실크로드

문제

현재 카자흐스탄이 있는 지역에는 예로부터 "실크로드" 라고 불리는 교역로가 있었다.

실크로드 위에는 N + 1 개의 도시가 있고, 서쪽부터 순서대로 도시 0, 도시 1, ... , 도시 N 이라고 번호가 붙어 있다. 도시 i - 1 과 도시 i 사이의 거리 (1 ≦ i ≦ N) 는 $D_{i}$ 이다.

무역상인 JOI 군은 도시 0 에서 출발하여 도시를 순서대로 거쳐 도시 N 까지 비단을 운반하게 되었다. 도시 0 에서 도시 N 까지 M 일 이내에 이동해야 한다. JOI 군은 각 날의 행동으로 다음 2 가지 중 하나를 고른다.

• 이동: 현재 있는 도시에서 한 칸 동쪽에 있는 도시로 하루에 걸쳐 이동한다. 현재 도시 i - 1 (1 ≦ i ≦ N) 에 있는 경우에는 도시 i 로 이동한다.
• 대기: 이동하지 않고 현재 있는 도시에서 하루 동안 대기한다.

이동은 힘들기 때문에, 이동할 때마다 피로도가 쌓여 간다. 실크로드에서는 날마다 날씨의 변동이 있으며, 날씨가 나쁜 날일수록 이동에 더 큰 고생이 따른다.

JOI 군이 비단을 운반하는 데 쓸 수 있는 M 일 중 j 일째 (1 ≦ j ≦ M) 의 날씨의 나쁜 정도가 $C_{j}$ 임을 알고 있다. 도시 i - 1 에서 도시 i (1 ≦ i ≦ N) 로 j 일째 (1 ≦ j ≦ M) 에 이동하는 경우, 피로도가 $D_{i}$ × $C_{j}$ 만큼 쌓인다. 이동하지 않고 대기하는 날에는 피로도가 쌓이지 않는다.

JOI 군은 각 날의 행동을 잘 골라서 가능한 한 피로도를 적게 쌓으면서 이동하고 싶다. JOI 군이 M 일 이내에 도시 N 으로 이동할 때, 이동을 시작해서 끝낼 때까지 쌓이는 피로도의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 1 + N + M 개의 줄로 이루어진다.

첫째 줄에는 2 개의 정수 N, M (1 ≦ N ≦ M ≦ 1000) 이 공백으로 구분되어 주어진다. 이는 실크로드가 N + 1 개의 도시로 이루어져 있고, JOI 군이 비단을 도시 0 에서 도시 N 까지 M 일 이내에 운반해야 함을 나타낸다.

이어지는 N 개의 줄 중 i 번째 줄 (1 ≦ i ≦ N) 에는 정수 $D_{i}$ (1 ≦ $D_{i}$ ≦ 1000) 가 주어진다. 이는 도시 i - 1 과 도시 i 사이의 거리가 $D_{i}$ 임을 나타낸다.

이어지는 M 개의 줄 중 j 번째 줄 (1 ≦ j ≦ M) 에는 정수 $C_{j}$ (1 ≦ $C_{j}$ ≦ 1000) 가 주어진다. 이는 j 일째의 날씨의 나쁜 정도가 $C_{j}$ 임을 나타낸다.

출력

JOI 군이 M 일 이내에 도시 N 으로 이동할 때, 이동을 시작해서 끝낼 때까지 쌓이는 피로도의 합의 최솟값을 한 줄에 출력한다.

예제 입력 1

3 5
10
25
15
50
30
15
40
30

예제 출력 1

1125

예제 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 이다. 이것이 최솟값이다.

예제 입력 2

2 6
99
20
490
612
515
131
931
1000

예제 출력 2

31589