비행맨

시간 제한3초메모리 제한1024 MB

요약
산 마을의 왼쪽 끝에서 오른쪽 끝까지 이동하는 최소 체력을 구한다. 나는 상태 전환과 T=1, T=2에 따른 낙하 비용을 고려해야 한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 그래프, 최단 경로, 수학
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

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

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

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

입력

첫 번째 줄에 두 정수 NN, TT가 공백으로 구분되어 주어진다.

두 번째 줄에 NN개의 정수 H_1,H_2,…,H_NH\_1, H\_2, \ldots, H\_N이 공백으로 구분되어 주어진다.

세 번째 줄에 N−1N-1개의 정수 A_1,A_2,…,A_N−1A\_1, A\_2, \ldots, A\_{N-1}이 공백으로 구분되어 주어진다.

네 번째 줄에 NN개의 정수 C_1,C_2,…,C_NC\_1, C\_2, \ldots, C\_N이 공백으로 구분되어 주어진다.

다섯 번째 줄에 N−1N-1개의 정수 F_1,F_2,…,F_N−1F\_1, F\_2, \ldots, F\_{N-1}이 공백으로 구분되어 주어진다.

출력

문제의 정답을 출력한다.

제한

  • 2≤N≤1052 \le N \le 10^5
  • 1≤T≤21 \le T \le 2
  • 1≤H_i≤N1 \le H\_i \le N, 1≤C_i≤1061 \le C\_i \le 10^6 (1≤i≤N1 \leq i \leq N)
  • 1≤A_i,F_i≤1091 \le A\_i, F\_i \le 10^9 (1≤i≤N−11 \leq i \leq N-1)
  • ∣H_i−H_i+1∣=1\left\lvert H\_i - H\_{i+1} \right\rvert = 1 (1≤i≤N−11 \leq i \leq N-1)

예제2

  1. 예제 1

    입력
    10 1
2 1 2 3 4 3 2 3 4 5
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
    예상 출력
    58

  2. 예제 2

    입력
    10 2
2 1 2 3 4 3 2 3 4 5
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
    예상 출력
    37