Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
G. Armed Soldiers 1
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two independent parts of this problem. The common part is highlighted in italics.

There are $$$n$$$ soldiers positioned at locations $$$a_i$$$, each armed with a gun of power $$$p_i$$$.

Whenever they spot a monster with a shield with $$$s$$$ standing at location $$$d$$$, each soldier fires a bullet towards it. The bullet starts with an initial effective power of $$$p_i$$$, but due to air resistance, this power decreases by 1 for every unit the bullet travels.

The Bullet will hit the monster if the effective power is greater than or equal to the shield width. Then let the number of bullets that hit the monster be $$$c(d,s)$$$

Formally, let $$$c(d,s)$$$ be the number of $$$1 \leq i\leq n$$$ such that $$$|a_i - d| \leq p_i - s$$$.

You are a monster and can survive no more than $$$k$$$ bullet hits on you. What minimum shield width would you choose so that you can stand anywhere and survive?

Clarification: The shield width must be a non-negative integer, the position of the monster must be an integer.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1\leq t\leq 10^4)$$$ — the number of test cases. This is followed by the description of the test cases.

The first line contains two integers $$$n \:(1\leq n \leq 10^5)$$$ and $$$k \:(0\leq k \leq n)$$$.

The second line contains $$$n$$$ integers $$$a_i \:(1\leq a_i \leq 10^9)$$$ denoting the location of the $$$i^{\mathrm{th}}$$$ soldier.

The third line contains $$$n$$$ integers $$$p_i \:(0\leq p_i \leq 10^9)$$$ denoting the power of the $$$i^{\mathrm{th}}$$$ soldier.

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

Output

For each test case, output a single integer $$$s$$$ the minimum shield width so that you can stand anywhere and survive.

Example
Input
2
4 1
2 3 2 4
1 0 1 0
10 7
17 5 7 17 17 5 6 9 2 8
24 1 21 29 28 19 23 9 25 11
Output
2
12
Note

For the first testcase

If $$$s \leq 1$$$, You will die at $$$d = 2$$$ ($$$\because$$$ Bullet of Soldier 1 and Soldier 3 will hit you)

It can be shown that you will survive with $$$s = 2$$$ no matter where you stand.