题目描述

你有 $n$ 张蛇咬。第 $i$ 张蛇咬的效果是使敌人获得 $v_i$ 层中毒，而且你知道它会在第 $t_i$ 回合抽上手。

你非常喜欢蛇咬，所以你会在抽到蛇咬时立刻将其打出。你中等的卡组大小保证了在 $10^{18}$ 回合内，每张蛇咬都只会恰好抽上手一次。

“中毒”机制的效果如下：如果敌人有至少 $1$ 层中毒，就会在本回合结束时受到等同于当前中毒层数的伤害，然后失去 $1$ 层中毒。

幸运的是，你遇到了特殊事件，因此可以进行至多 $k$ 次附魔。一次附魔可以使一张蛇咬的 $v_i$ 增加 $1$，并且可以对同一张蛇咬进行多次附魔。

你马上就要挑战建筑师了。为了简化问题，战斗持续 $10^{18}$ 回合，敌人不会做任何事情，而你只会打出蛇咬。

请问，在最优地进行附魔的情况下，你最多可以对敌人造成多少伤害？

输入格式

第一行输入两个整数 $c,t$，分别表示子任务编号和测试用例组数。

对于每组测试用例：

• 第一行输入两个整数 $n,k$；
• 第二行输入 $n$ 个正整数 $v_1,v_2,\ldots,v_n$；
• 第三行输入 $n$ 个正整数 $t_1,t_2,\ldots,t_n$。

输出格式

对于每组测试用例，输出一行一个正整数，表示答案。

样例 1

输入

0 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

数据范围

记 $N$ 为所有测试用例中 $n$ 的总和。

对于所有数据：

$$1\le t\le 10^4, \qquad 1\le n,N\le 3\times 10^5,$$ $$0\le k\le 10^9, \qquad 1\le v_i, \qquad \sum_{i=1}^{n}v_i\le 10^9, \qquad 1\le t_i\le 10^9.$$

子任务编号	分值	$N\le$	$k\le$
1	30	$3\times 10^5$	$0$
2		$8000$	$10^9$
3	40	$3\times 10^5$