#P18099. The Best Card

The Best Card

The Best Card

题目描述

游戏持续 10100010^{1000} 个回合。敌人的初始毒性层数为 00。

有 nn 张卡牌。第 ii 张卡在第 tit_i 回合开始时使用,使毒性增加 viv_i 层。同一回合可以使用多张卡,毒性增加量相加。

每回合结束时,设当前毒性为 xx:若 x>0x>0,敌人受到 xx 点伤害,然后毒性减 11;若 x=0x=0,则什么也不发生。

游戏开始前,你可以强化 kk 次。每次任选一张卡,将其 viv_i 增加 11;同一张卡可以被重复强化。求进行这些强化后,敌人在整个游戏中受到的最大总伤害。

输入格式

第一行一个整数 TT。

每组数据包含三行:第一行两个整数 n,kn,k;第二行 nn 个整数 v1,…,vnv_1,\ldots,v_n;第三行 nn 个整数 t1,…,tnt_1,\ldots,t_n。

输出格式

每组数据输出一行,一个整数,表示最大总伤害。

数据范围

1≤T≤1041\le T\le10^4,1≤n≤3×1051\le n\le3\times10^5,0≤k≤1090\le k\le10^9;1≤vi,ti≤1091\le v_i,t_i\le10^9,每组数据满足 ∑ivi≤109\sum_i v_i\le10^9。一个输入文件中所有 nn 之和不超过 3×1053\times10^5。tit_i 不保证有序,也不保证互不相同。

样例 1

输入

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