I. Fireflies Lead the Way
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

At night, there are $$$n$$$ firefly lamps lit along the riverbank. The $$$i$$$-th lamp is located at coordinate $$$x_i$$$, and they are arranged from left to right along the river, i.e., $$$$$$ x_1 \lt x_2 \lt \cdots \lt x_n $$$$$$ XqAiyee wants to walk from the $$$1$$$-st lamp to the $$$n$$$-th lamp.

When she is at the $$$i$$$-th lamp ($$$1 \le i \le n-1$$$), she can choose:

  1. Stroll along the bank. Walk along the riverbank to the $$$(i+1)$$$-th lamp, consuming stamina $$$a_i$$$.
  2. Fireflies lead the way. Choose an index $$$j$$$ ($$$i + 1 \le j \le n$$$), and follow the fireflies to the $$$j$$$-th lamp, consuming stamina $$$b_i + (x_j - x_i)^2$$$.

Since the fireflies will get tired, XqAiyee can use "Fireflies lead the way" at most $$$k$$$ times.

Please determine the minimum stamina required for XqAiyee to reach the $$$n$$$-th lamp.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 2 \times 10^{5}$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$2 \leq n \leq 2 \times 10^5$$$, $$$0 \leq k \leq 200$$$) — the number of firefly lamps and the maximum number of times "Fireflies lead the way" can be used.

The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \cdots, x_n$$$ ($$$-10^5 \leq x_1 \lt x_2 \lt \cdots \lt x_n \leq 10^5$$$) — the coordinates of the lamps.

The third line of each test case contains $$$n - 1$$$ integers $$$a_1, a_2, \cdots, a_{n-1}$$$ ($$$0 \leq a_i \leq 10^5$$$).

The fourth line of each test case contains $$$n - 1$$$ integers $$$b_1, b_2, \cdots, b_{n-1}$$$ ($$$0 \leq b_i \leq 10^5$$$).

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

Output

For each test case, output a single integer — the minimum stamina required for XqAiyee to reach the $$$n$$$-th lamp.

Example
Input
2
5 1
0 2 3 7 10
3 2 100 2
1 5 0 4
4 2
-3 0 4 5
2 100 2
0 1 0
Output
23
20