E. Bad Luck Blackie
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bad Luck Blackie is a 1949 American animated comedy short film. They launched a new game recently where they give you an array $$$a$$$ of $$$n$$$ integer numbers, and an array $$$b$$$ of $$$n$$$ integer numbers. Initially, your score is zero.

In each second, you do the following operations in the same order:

  • Choose an integer number $$$1 \le pos \le n$$$ as the Bad Luck Blackie.
  • Add $$$a_{pos}$$$ to your score.
  • Assign $$$a_{pos} := a_{pos} - b_{pos}$$$. Note that $$$a_{pos}$$$ can be negative after the assignment.
  • For each $$$(1 \le i \le n, i \ne pos)$$$, assign $$$a_i := min(a_i + b_i, the\ initial\ value\ of\ a_i\ before\ doing\ any\ operations)$$$.

Your task is to find the maximum score you can get after $$$k$$$ seconds. Can you win the game?

Input

The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 10^5)$$$. The number of test cases.

The first line of each test case contains two space-separated integer numbers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 2 \times 10^5, 1 \le k \le 10^9)$$$. The number of integer numbers in $$$a$$$ and the number of seconds of the game, respectively.

The second line of each test case contains $$$n$$$ space-separated integer numbers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$, where $$$a_i$$$ is the $$$i-th$$$ number of $$$a$$$.

The third line of each test case contains $$$n$$$ space-separated integer numbers $$$b_i$$$ $$$(1 \le b_i \le 10^9)$$$, where $$$b_i$$$ is the $$$i-th$$$ number of $$$b$$$.

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

Output

For each test case print a single line containing a single integer number. the maximum score you can get after $$$k$$$ seconds.

Example
Input
1
2 3
5 3
1 1
Output
13