E. Cyclic Shifts
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas has two arrays $$$a$$$ and $$$b$$$ both of length $$$n$$$, as well as a value $$$k$$$. He can perform the following operations on $$$a$$$:

  1. Choose an index $$$1\leq i\leq n$$$, and set $$$a_i:=a_i+1$$$
  2. Choose an index $$$1\leq i\leq n$$$, and set $$$a_i:=a_i-1$$$
  3. Choose an index $$$1\leq i\leq n-k+1$$$, and cyclically shift the subarray $$$[i, i + k - 1]$$$ to the left. This operation can be done at most once.

A cyclic shift on a subarray $$$[l,r]$$$ of array $$$a$$$ assigns $$$a_i:=a_{i+1}$$$ for $$$l\leq i \lt r$$$ and $$$a_r:=a_l$$$.

Help Thomas find the minimum number of operations to make the two arrays equal.

Input

The first line of the test data contains an integer $$$t$$$ ($$$1\leq t\leq 5\cdot 10^3$$$), denoting the number of test cases.

The first line of each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k\leq n\leq 2\cdot 10^5)$$$, the length of the arrays and the length of the cyclic shift.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$), denoting the elements of $$$a$$$.

The third line of each testcase contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1\leq b_i\leq 10^9$$$), denoting the elements of $$$b$$$.

The sum of $$$n$$$ over all testcases will not exceed $$$2\cdot 10^5$$$.

Testcases in subtasks are numbered $$$1 - 20$$$ with samples skipped.

Testcases $$$1 - 5$$$ satisfy sum of $$$n$$$ less than or equal to $$$10^3$$$.

The remaining testcases do not satisfy any additional constraints.

Output

Output one integer per test case on its own line that is the minimum number of operations to make $$$a$$$ and $$$b$$$ equal. Note that this number may not fit in a $$$32$$$-bit integer.

Examples
Input
3
3 2
1 7 3
1 7 3
5 5
1 2 3 4 5
2 3 4 5 1
5 3
5 3 9 10 1
7 1 2 1 3
Output
0
1
19
Input
1
7 6
964699482 819602309 115120245 28925241 945810909 184051745 67111980
796467029 780414521 690030775 504722824 778691724 529821700 720973391
Output
2424878905
Note

In the first test case, the arrays are already equal so the answer is $$$0$$$.

In the second test case, the arrays can be made equal with one cyclic shift, so the answer is $$$1$$$.

In the third test case, one way to get $$$19$$$ operations is to rotate the subarray $$$[3, 5]$$$.

Idea: dutin

Preparation: dutin

Occurrences: Novice 5, Advanced 2