13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T629,

Sparkle gives you two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Initially, your score is $$$0$$$. In one operation, you can choose an integer $$$i$$$ and add $$$a_i$$$ to your score. Then, you must set $$$a_i$$$ = $$$\max(0, a_i - b_i)$$$.

You only have time to perform $$$k$$$ operations before Sparkle sets off a nuclear bomb! What is the maximum score you can acquire after $$$k$$$ operations?

Input

The first line contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — the length of the arrays and the number of operations you can perform.

The following line contains $$$n$$$ integers $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The following line contains $$$n$$$ integers $$$b_1, b_2, ... b_n$$$ ($$$1 \leq b_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Bomb

Examples