지금 카자흐스탄이 있는 지역에는 예전에 「실크로드」라 불리던 교역로가 있었다. 실크로드 위에는 도시가 \(N+1\)개 있고, 서쪽부터 도시 \(0\), 도시 \(1\), \(\ldots\), 도시 \(N\)으로 번호가 붙어 있다. 도시 \(i-1\)과 도시 \(i\) 사이의 거리(\(1 \le i \le N\))는 \(D_i\)이다. 무역상 JOI 군은 도시 \(0\)에서 출발해 도시를 차례로 거쳐 도시 \(N\)까지 비단을 나르기로 했다. 도시 \(0\)에서 도시 \(N\)까지 \(M\)일 이내에 이동해야 한다. JOI 군은 각 날의 행동으로 다음 둘 중 하나를 고른다. 이동: 지금 있는 도시에서 바로 동쪽 도시로 \(1\)일을 들여 이동한다. 지금 도시 \(i-1\)(\(1 \le i \le N\))에 있으면 도시 \(i\)로 이동한다. 대기: 이동하지 않고 지금 있는 도시에서 \(1\)일 기다린다. 이동은 힘들고, 이동할 때마다 피로가 쌓인다. 실크로드는 날마다 날씨가 바뀌고, 날씨가 나쁠수록 이동이 더 힘들다. JOI 군이 비단을 나르는 데 쓸 수 있는 \(M\)일 가운데 \(j\)일째(\(1 \le j \le M\))의 날씨 나쁨은 \(C_j\)로 알려져 있다. 도시 \(i-1\)에서 도시 \(i\)(\(1 \le i \le N\))로 \(j\)일째(\(1 \le j \le M\))에 이동하면 피로가 \(D_i \times C_j\)만큼 쌓인다. 이동하지 않고 기다리는 날에는 피로가 쌓이지 않는다. JOI 군은 각 날의 행동을 잘 골라 피로를 되도록 적게 쌓고 싶다. \(M\)일 이내에 도시 \(N\)으로 이동할 때, 이동을 시작해 끝날 때까지 쌓이는 피로 합의 최솟값을 구하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(M\)
\(D_1\)
\(\vdots\)
\(D_N\)
\(C_1\)
\(\vdots\)
\(C_M\)
- 입력은 \(1+N+M\)줄이다.
- 첫째 줄에 정수 \(N\), \(M\)이 공백 하나로 구분되어 주어진다. 실크로드가 도시 \(N+1\)개로 이루어지고, JOI 군이 비단을 도시 \(0\)에서 도시 \(N\)까지 \(M\)일 이내에 날라야 함을 나타낸다.
- 이어지는 \(N\)줄 가운데 \(i\)번째 줄(\(1 \le i \le N\))에 정수 \(D_i\)가 주어지고, 도시 \(i-1\)과 도시 \(i\) 사이의 거리가 \(D_i\)임을 나타낸다.
- 이어지는 \(M\)줄 가운데 \(j\)번째 줄(\(1 \le j \le M\))에 정수 \(C_j\)가 주어지고, \(j\)일째의 날씨 나쁨이 \(C_j\)임을 나타낸다.
- \(1 \le N \le M \le 1000\)
- \(1 \le D_i \le 1000\)
- \(1 \le C_j \le 1000\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 JOI 군이 \(M\)일 이내에 도시 \(N\)으로 이동할 때 쌓이는 피로 합의 최솟값을 출력한다.
\(1\)일째는 기다린다. \(2\)일째에 도시 \(0\)에서 \(1\)로 이동하면 피로는 \(10 \times 30 = 300\)이다. \(3\)일째에 도시 \(1\)에서 \(2\)로 이동하면 \(25 \times 15 = 375\)이다. \(4\)일째는 기다린다. \(5\)일째에 도시 \(2\)에서 \(3\)으로 이동하면 \(15 \times 30 = 450\)이다. 합은 \(300+375+450=1125\)이고, 이것이 최솟값이다.