33OJ
登录 注册

#P17502. [ICPC 2026 Wuhan I] The Best Card

    ID: 20230 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>ICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] The Best Card

Problem Description

Snakebite is the most powerful card in the game Slay the Spire 2, and Yuki enjoys using it to defeat enemies.

The game lasts for 10100010^{1000} turns. At the start of the game, the enemy has 00 layers of poison.

Yuki has nn snakebite cards in total. The effect of the ii-th snakebite is: when played, it increases the enemy's poison layers by viv_i. Yuki will play the ii-th snakebite at the start of the tit_i-th turn.

At the end of each turn, let xx be the number of poison layers on the enemy:

  • If x=0x=0, nothing happens;
  • If x≠0x\ne0, the enemy takes xx damage, and the number of poison layers decreases by 11, i.e., x←x−1x\leftarrow x-1.

To maximize the total damage dealt to the enemy, Yuki can perform kk enchantments before the game begins. In each enchantment, Yuki chooses a positive integer i≤ni \le n and increases the value of viv_i by 11. The same index ii can be selected multiple times.

You need to determine the maximum damage the enemy can receive after Yuki performs kk enchantments.

Input Format

Each test contains multiple test cases.

The first line contains an integer tt (1≤t≤1041 \le t \le 10^4), representing the number of test cases.

For each test case:

  • The first line contains two integers n,kn,k (1≤n≤3⋅1051 \le n \le 3\cdot10^5, 0≤k≤1090 \le k \le 10^9).
  • The second line contains nn integers v1,v2,⋯ ,vnv_1,v_2,\cdots,v_n (1≤vi≤1091 \le v_i \le 10^9, 1≤∑vi≤1091 \le \sum v_i \le 10^9).
  • The third line contains nn integers t1,t2,⋯ ,tnt_1,t_2,\cdots,t_n (1≤ti≤1091 \le t_i \le 10^9).

It is guaranteed that the sum of nn over all test cases does not exceed 3⋅1053\cdot10^5.

Output Format

For each test case, output a single line containing an integer representing the maximum damage the enemy can receive after Yuki performs kk enchantments.

5
2 1
2 3
1 4
2 2
3 4
1 3
4 1
3 3 1 4
4 4 1 5
3 0
16 27 62
9 88 11
3 5
9 3 1
8 3 3
13
37
63
3335
126