You are given two integer arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$, and a total number of turns $$$k$$$.

Alice and Bob play a game by taking turns modifying array $$$a$$$. Alice goes first. The game lasts for exactly $$$k$$$ turns.

On their turn, a player must choose an index $$$i$$$ ($$$1 \leq i \leq n$$$) and perform one of the following operations:

Add: Increase $$$a_i$$$ by $$$b_i$$$, i.e., set $$$a_i := a_i + b_i$$$.
Subtract: Decrease $$$a_i$$$ by $$$b_i$$$, i.e., set $$$a_i := a_i - b_i$$$.

After the $$$k$$$-th turn is complete, the final score is calculated as the maximum non-empty subarray sum of the modified array $$$a$$$. Alice's goal is to maximize the final score, while Bob's goal is to minimize the final score.

Assuming both players play optimally to achieve their respective goals, determine the final score.

The maximum non-empty subarray sum of $$$a$$$ is defined as $$$\max_{1 \leq i \leq j \leq n} S(i, j)$$$, where $$$S(i, j) = a_i + a_{i+1} + \cdots + a_j$$$. Note that empty subarrays are not considered.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$1 \le k \le 2\cdot 10^5$$$) — the length of the arrays and the total number of turns.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_{n}$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_{n}$$$ ($$$0 \le b_i \le 10^9$$$) — the elements of array $$$b$$$.

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

Output

For each test case, print a single integer — the final score after $$$k$$$ turns, assuming both players play optimally.

Note

For the first test case:

Any move can't change the array $$$a$$$ because all elements in $$$b$$$ are zero.
The maximum non-empty subarray sum of this final array is $$$3 + (-1) + 9 = 11$$$.

For the second test case, one of the possible optimal sequences of moves is:

Alice adds $$$b_3=1$$$ to $$$a_3$$$. Array $$$a$$$ becomes $$$[10, 10, 11, 10]$$$.
Bob subtracts $$$b_1=1$$$ from $$$a_1$$$. Array $$$a$$$ becomes $$$[9, 10, 11, 10]$$$.
Alice adds $$$b_3=1$$$ to $$$a_3$$$. Array $$$a$$$ becomes $$$[9, 10, 12, 10]$$$.
Bob subtracts $$$b_1=1$$$ from $$$a_1$$$. Array $$$a$$$ becomes $$$[8, 10, 12, 10]$$$.
Alice adds $$$b_4=1$$$ to $$$a_4$$$. Array $$$a$$$ becomes $$$[8, 10, 12, 11]$$$.
The maximum non-empty subarray sum of this final array is $$$8+10+12+11 = 41$$$.

For the third test case, one of the possible optimal sequences of moves is:

Alice adds $$$b_2=11$$$ to $$$a_2$$$. Array $$$a$$$ becomes $$$[2, 4, 3]$$$.
The maximum non-empty subarray sum of this final array is $$$2 + 4 + 3 = 9$$$.

For the fourth test case, one of the possible optimal sequences of moves is:

Alice adds $$$b_2=11$$$ to $$$a_2$$$. Array $$$a$$$ becomes $$$[2, 4, 3]$$$.
Bob subtracts $$$b_2=11$$$ from $$$a_2$$$. Array $$$a$$$ becomes $$$[2, -7, 3]$$$.
The maximum non-empty subarray sum of this final array is $$$3$$$.

Idx	Name	Rating
A	Suspension	800
B	Split	1200
C	Annoying Game	1400
D	Palindrome Flipping	2000
E	Sink	2600
F1	Distinct GCDs (Easy Version)	2600
F2	Distinct GCDs (Hard Version)	3000

Codeforces Round 1067 (Div. 2)