P17502 [ICPC 2026 Wuhan I] The Best Card

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 $10^{1000}$ turns. At the start of the game, the enemy has $0$ layers of poison. Yuki has $n$ snakebite cards in total. The effect of the $i$-th snakebite is: when played, it increases the enemy's poison layers by $v_i$. Yuki will play the $i$-th snakebite at the start of the $t_i$-th turn. At the end of each turn, let $x$ be the number of poison layers on the enemy: - If $x=0$, nothing happens; - If $x\ne0$, the enemy takes $x$ damage, and the number of poison layers decreases by $1$, i.e., $x\leftarrow x-1$. To maximize the total damage dealt to the enemy, Yuki can perform $k$ enchantments before the game begins. In each enchantment, Yuki chooses a positive integer $i \le n$ and increases the value of $v_i$ by $1$. The same index $i$ can be selected multiple times. You need to determine the maximum damage the enemy can receive after Yuki performs $k$ enchantments.

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$), representing the number of test cases. For each test case: - The first line contains two integers $n,k$ ($1 \le n \le 3\cdot10^5$, $0 \le k \le 10^9$). - The second line contains $n$ integers $v_1,v_2,\cdots,v_n$ ($1 \le v_i \le 10^9$, $1 \le \sum v_i \le 10^9$). - The third line contains $n$ integers $t_1,t_2,\cdots,t_n$ ($1 \le t_i \le 10^9$). It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$.

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