33630번 - 비행맨 서브태스크

문제

산으로 이루어진 마을에 사람들이 살고 있다. 산 마을은 좌표평면상의 $N$개의 점으로 이루어져 있다. 이 점들을 $x$좌표가 증가하는 순서대로 연결하면 산 마을의 모양이 된다. 1ドル \leq i \leq N$인 모든 정수 $i$에 대해, $i$번째 점의 위치는 $(i, H_i)$이다. 이때, $\left\lvert H_i - H_{i+1} \right\rvert = 1$ (1ドル \leq i \leq N-1$)이다. 산 마을의 입구는 산 마을의 왼쪽 끝점으로, $(1, H_1)$이다. 마찬가지로 산 마을의 출구는 산 마을의 오른쪽 끝점으로, $(N, H_N)$이다.

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

우현이는 산 마을의 입구에서 출발해 산 마을의 출구에서 나가려고 한다. 우현이의 상태는 항상 '걷는 상태'와 '나는 상태' 중 하나이다. 처음에 입구에서 우현이는 '걷는 상태'에서 시작한다. 출구에 도착하지 않았을 때, 우현이는 다음과 같이 행동할 수 있다.

1. '걷는 상태'인 경우 (이때 우현이는 $(i, H_i)$에 있다고 하자)

• 걸어서 $(i+1, H_{i+1})$로 이동할 수 있다. 이때, $A_i$의 체력이 소모된다.
• 위치를 바꾸지 않고 '나는 상태'로 바꿀 수 있다. 체력은 소모되지 않는다.

2. '나는 상태'인 경우 (이때 우현이는 $(i, j)$에 있다고 하자)

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

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

입력

첫 번째 줄에 두 정수 $N,ドル $T$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $H_1, H_2, \ldots, H_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $N-1$개의 정수 $A_1, A_2, \ldots, A_{N-1}$이 공백으로 구분되어 주어진다.

네 번째 줄에 $N$개의 정수 $C_1, C_2, \ldots, C_N$이 공백으로 구분되어 주어진다.

다섯 번째 줄에 $N-1$개의 정수 $F_1, F_2, \ldots, F_{N-1}$이 공백으로 구분되어 주어진다.

출력

문제의 정답을 출력한다.

제한

• 2ドル \le N \le 10^5$
• 1ドル \le T \le 2$
• 1ドル \le H_i \le N,ドル 1ドル \le C_i \le 10^6$ (1ドル \leq i \leq N$)
• 1ドル \le A_i, F_i \le 10^9$ (1ドル \leq i \leq N-1$)
• $\left\lvert H_i - H_{i+1} \right\rvert = 1$ (1ドル \leq i \leq N-1$)

서브태스크

힌트