People live in a village made of mountains. The mountain village consists of $N$ points on a coordinate plane. Connecting these points in increasing order of their x-coordinates forms the shape of the mountain village. For every $i$, the position of the $i$-th point is $(i, H_i)$ (it is guaranteed that $\left\lvert H_i - H_{i+1} \right\rvert = 1$).

The entrance to the mountain village is the leftmost point, $(1, H_1)$. Similarly, the exit of the mountain village is the rightmost point, $(N, H_N)$.

Gravity in the mountain village acts in a peculiar way, and there are two ways gravity can act, represented by a variable $T$ which has a value of 1 or 2.

Woohyun wants to start at the entrance of the mountain village and exit through the exit.

Woohyun's state is always one of 'walking' or 'flying'. Initially, at the entrance, Woohyun starts in the 'walking' state.

When not yet at the exit, Woohyun can act as follows:

1. If in the 'walking' state (Woohyun is at $(i, H_i)$):

2. Can walk to $(i+1, H_{i+1})$. In this case, $A_i$ stamina is consumed.

3. Can change to the 'flying' state without changing position.

4. If in the 'flying' state (Woohyun is at $(i, j)$):

5. If $i \le N-1$ and $H_{i+1} \le j$, can fly to $(i+1, j)$. In this case, $F_i$ stamina is consumed.

6. Can move to $(i, H_i)$ via free fall and change to the 'walking' state. In this case, if $T = 1$, $\left\lfloor \sqrt {j - H_i} \right\rfloor \times C_i$ stamina is consumed, and if $T = 2$, $(j - H_i) \times C_i$ stamina is consumed.

Write a program to find the minimum stamina required for Woohyun to go from the entrance to the exit of the mountain village.

Input

The first line contains $N$ and $T$.

The second line contains $H_1, H_2, \ldots, H_N$ separated by spaces.

The third line contains $A_1, A_2, \ldots, A_{N-1}$ separated by spaces.

The fourth line contains $C_1, C_2, \ldots, C_N$ separated by spaces.

The fifth line contains $F_1, F_2, \ldots, F_{N-1}$ separated by spaces.

($2 \le N \le 10^5, 1 \le T \le 2$, for all $i$, $1 \le H_i \le N$, $1 \le A_i, F_i \le 10^9$, $1 \le C_i \le 10^6$, and it is satisfied that $\left\lvert H_i - H_{i+1} \right\rvert = 1$ for all $i$.)

Output

Output the answer to the problem on the first line.

Subtasks

1. (2 points) Satisfies $H_i = i$ for all $i$.
2. (10 points) $T = 1, N \le 3000$
3. (10 points) $T = 2, N \le 3000$
4. (30 points) $T = 1, N \le 5 \times 10^4$
5. (18 points) $T = 2$, satisfies $H_i = N - i + 1$ for all $i$.
6. (30 points) $T = 2$

Examples

Input 1

10 1
1 2 3 2 3 2 1 2 1 2
4 9 10 4 9 8 2 8 10
1 1 2 10 5 9 2 4 7 8
2 6 7 4 7 9 4 6 7

Output 1

56

Input 2

10 2
1 2 3 2 3 4 5 4 3 2
2 2 6 4 8 3 1 1 10
9 6 1 8 4 4 3 2 4 5
10 2 3 3 8 6 3 2 9

Output 2

33