33OJ
登录 注册

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

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

[ICPC 2026 Wuhan I] The Best Card

题目描述

蛇咬是游戏《杀戮尖塔 2》中最强力的卡牌,Yuki 十分喜欢用这张卡打败敌人。

游戏一共会进行 10100010^{1000} 个回合。在游戏开始时,敌人的中毒层数为 00。

Yuki 共拥有 nn 张蛇咬,第 ii 张蛇咬的效果是:在打出时使敌人的中毒层数增加 viv_i。Yuki 会在第 tit_i 个回合开始时打出第 ii 张蛇咬。

在每个回合结束时,设敌人的中毒层数为 xx:

  • 若 x=0x=0,则无事发生;
  • 若 x≠0x\ne0,则敌人受到 xx 点伤害,且中毒层数减少 11,即 x←x−1x\leftarrow x-1。

为了使敌人受到尽可能多的伤害,在游戏开始前,Yuki 可以进行 kk 次附魔。每次附魔,Yuki 需要选择一个不大于 nn 的正整数 ii,将 viv_i 的值增加 11。同一个正整数 ii 可以被选择多次。

你需要求出,在 Yuki 进行 kk 次附魔后,敌人最多会受到多少点伤害。

输入格式

本题包含多组测试数据。

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4),表示测试数据组数。

对于每组测试数据:

  • 第一行包含两个整数 n,kn,k(1≤n≤3⋅1051 \le n \le 3\cdot10^5,0≤k≤1090 \le k \le 10^9)。
  • 第二行包含 nn 个整数 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)。
  • 第三行包含 nn 个整数 t1,t2,⋯ ,tnt_1,t_2,\cdots,t_n(1≤ti≤1091 \le t_i \le 10^9)。

保证所有测试数据中 nn 的总和不超过 3⋅1053\cdot10^5。

输出格式

对于每组测试数据,输出一行,包含一个整数,表示在 Yuki 进行 kk 次附魔后,敌人最多会受到的伤害点数。

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