산으로 이루어진 마을에 사람들이 살고 있다. 산 마을은 좌표평면 상의 $N$개의 점으로 이루어져 있다. 이 점들을 x좌표가 증가하는 순서대로 연결하면 산 마을의 모양이 된다. 모든 $i$에 대해 $i$번째 점의 위치는 $(i, H_i)$이다.(단, $\left\lvert H_i - H_{i+1} \right\rvert = 1$임이 보장된다.)

산 마을의 입구는 산 마을의 왼쪽 끝점으로, $(1, H_1)$이다. 마찬가지로 산 마을의 출구는 산 마을의 오른쪽 끝점으로, $(N, H_N)$이다.

산 마을에는 중력이 특이하게 작용하는데, 중력이 작용할 수 있는 방법은 두 가지이고 이는 1 또는 2의 값을 갖는 $T$라는 변수로 표현된다.

우현이는 산 마을의 입구에서 출발해 산 마을의 출구에서 나가려고 한다.

우현이의 상태는 항상 '걷는 상태'와 '나는 상태' 중 하나이다. 처음에 입구에서 우현이는 '걷는 상태'에서 시작한다.

출구에 도착하지 않았을 때, 우현이는 다음과 같이 행동할 수 있다.

1. '걷는 상태'인 경우(우현이는 $(i, H_i)$에 있음)

2. 걸어서 $(i+1, H_{i+1})$로 이동할 수 있다. 이 때, $A_i$의 체력이 소모된다.

3. 위치를 바꾸지 않고 '나는 상태'로 바꿀 수 있다.

4. '나는 상태'인 경우(우현이는 $(i, j)$에 있음)

5. $i \le N-1$이고 $H_{i+1} \le j$인 경우 날아서 $(i+1, j)$로 이동할 수 있다. 이 때, $F_i$의 체력이 소모된다.

6. 자유낙하를 통해 $(i, H_i)$로 이동하고 '걷는 상태'로 바꿀 수 있다. 이 때, $T = 1$인 경우 $\left\lfloor \sqrt {j - H_i} \right\rfloor \times C_i$의 체력이 소모되고, $T = 2$인 경우 $(j - H_i) \times C_i$의 체력이 소모된다.

우현이가 산 마을의 입구에서 시작해 출구까지 가는데 필요한 최소의 체력을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 $N$, $T$가 주어진다.

둘째 줄에 $H_1, H_2, \ldots, H_N$이 공백을 사이에 두고 주어진다.

셋째 줄에 $A_1, A_2, \ldots, A_{N-1}$이 공백을 사이에 두고 주어진다.

넷째 줄에 $C_1, C_2, \ldots, C_N$이 공백을 사이에 두고 주어진다.

다섯째 줄에 $F_1, F_2, \ldots, F_{N-1}$이 공백을 사이에 두고 주어진다.

($2 \le N \le 10^5, 1 \le T \le 2$, 모든 $i$에 대해 $1 \le H_i \le N$, $1 \le A_i, F_i \le 10^9, 1 \le C_i \le 10^6$, 모든 $i$에 대해 $\left\lvert H_i - H_{i+1} \right\rvert = 1$을 만족한다.)

Output

첫째 줄에 문제의 정답을 출력한다.

Scoring

1. (2점) 모든 $i$에 대해 $H_i = i$을 만족한다.
2. (10점) $T = 1, N \le 3000$
3. (10점) $T = 2, N \le 3000$
4. (30점) $T = 1, N \le 5 \times 10^4$
5. (18점) $T = 2$, 모든 $i$에 대해 $H_i = N - i + 1$을 만족한다.
6. (30점) $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