시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 13 8 8 61.538%

문제

과거 카자흐스탄에는 "실크로드"라는 교역로가 있었다.

실크로드는 N + 1 개의 도시가 있고, 서쪽부터 도시 0, 도시 1, ..., 도시 N이다. 도시 i - 1과 도시 i (1 ≦ i ≦ N) 사이의 거리는 Di이다.

무역상인 JOI 군은 도시 0에서 출발하여 도시를 차례로 경유하여 도시 N까지 실크로드를 수행하게 되었다. 도시 0에서 도시 N까지 M 이내에 이동해야한다. JOI 군은 각각의 날에 다음 두 가지 중 하나를 선택한다.

  • 이동 : 현재의 도시에서 동쪽의 도시로 1 일 걸쳐 이동한다. 현재 도시 i - 1 (1 ≦ i ≦ N)에 있다면, 도시 i로 이동합니다.
  • 대기 : 이동하지 않고 현재 도시에서 1 일 대기한다.

그러나, 이동 할 때마다 피로도가 쌓여 간다. 실크로드에서는 매일 날씨변화가 나쁜 정도에 따라 이동에 어려움이 측정된다.

JOI 군은 M 일 중 j 일째 (1 ≦ j ≦ M)의 날씨가 Cj임을 알고있다. 도시 i - 1에서 도시 i (1 ≦ i ≦ N)에 j 일째 (1 ≦ j ≦ M)로 이동하는 경우, 피로도가 Di × Cj 만 쌓여 버린다. 이동하지 않고 기다리는 날은 피로도가 쌓이지 않는다.

JOI 군은 각각의 날에 행동을 잘 선택하여 가능한 피로도를 적게해서 이동하고 싶다. JOI 군이 M 이내에 도시 N으로 이동할 때의 피로도 총합의 최소를 구해라.

입력

입력은 1 + N + M 행으로 구성된다.

첫 번째 줄에는 두 개의 정수 N, M (1 ≦ N ≦ M ≦ 1000)가 공백을 구분으로 쓰여져있다.  이것은 실크로드가 N + 1 개의 도시로 구성되며, JOI 군이 실크를 도시 0에서 도시 N까지 M 이내에 실시해야한다는 것을 나타낸다.

다음 N 라인 중 i 번째 줄 (1 ≦ i ≦ N)에는 정수 Di (1 ≦ Di ≦ 1000)가 적혀있다. 이것은 도시 i - 1과 도시 i 사이의 거리가 Di임을 나타낸다.

다음 M 라인 중 j 번째 줄 (1 ≦ j ≦ M)에는 정수 Cj (1 ≦ Cj ≦ 1000)가 적혀있다. 이것은 j 일째 날씨 나쁨정도가 Cj임을 나타낸다.

출력

JOI 군이 M 이내에 도시 N으로 이동할 때의 피로도 총합의 최소를 한 줄로 출력하라.

예제 입력

3 5
10
25
15
50
30
15
40
30

예제 출력

1125

예제 입력 2

2 6
99
20
490
612
515
131
931
1000

예제 출력 2

31589

힌트

입출력 예 1에서 쌓이는 피로도의 합계를 최소화하도록 JOI 군이 이동하려면 다음과 같이한다.

  • 1 일째는 대기한다.
  • 2 일째에 도시 0 -> 도시 1로 이동한다. 이 때 쌓이는 피로도는 10 × 30 = 300이다.
  • 3 일째에 도시 1 -> 도시 2로 이동한다. 이 때 쌓이는 피로도는 25 × 15 = 375이다.
  • 4 일째는 대기한다.
  • 5 일째에 도시 2 -> 도시 3로 이동합니다. 이 때 쌓이는 피로도는 15 × 30 = 450이다.

JOI 군이 이렇게 이동 한 경우에 쌓이는 피로도의 합계는 300 + 375 + 450 = 1125이다. 이것이 최소이다.