컨베이어 벨트

시간 제한1초메모리 제한128 MB

요약

작업자별 기본 시간과 자동차별 복잡도가 주어질 때, 순차적 전달 제약을 지키면서 모든 자동차를 완료하는 최소 총 시간을 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

한 자동차 공장에는 N명의 직원이 일렬로 배치되어 있다. 직원은 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 매겨져 있으며, 각 직원이 맡은 작업은 서로 다르다.

자동차 한 대는 직원 1, 직원 2, ..., 직원 N의 순서로 작업을 거치면 완성된다. 자동차는 1번부터 M번까지 순서대로 생산해야 한다. 직원 i의 기본 작업 시간이 T_i이고 자동차 j의 복잡도가 F_j라면, 직원 i가 자동차 j에 대한 작업을 끝내는 데 걸리는 시간은 T_i * F_j이다.

어떤 직원이 자신의 작업을 끝내면 그 자동차는 즉시 다음 직원에게 넘어간다. 이때 다음 직원이 다른 자동차를 작업 중이면 안 된다. 따라서 직원 1은 필요한 경우 새 자동차 작업을 시작하기 전에 기다려서, 어떤 전달 시점에도 다음 직원이 바쁘지 않도록 해야 한다.

모든 직원의 작업 시간과 모든 자동차의 복잡도가 주어진다. 모든 자동차를 완성하는 데 필요한 최소 시간을 구하라.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000)

다음 N개 줄에는 직원 i의 기본 작업 시간 T_i가 한 줄에 하나씩 주어진다. (1 ≤ T_i ≤ 10,000)

다음 M개 줄에는 자동차 j의 복잡도 F_j가 한 줄에 하나씩 주어진다. (1 ≤ F_j ≤ 10,000)

출력

모든 자동차를 완성하는 데 필요한 최소 시간을 하나의 정수로 출력한다.

예제3

예제 1
입력
```
3 3
2
1
1
2
1
1
```
예상 출력
```
11
```
예제 2
입력
```
3 3
2
3
3
2
1
2
```
예상 출력
```
29
```
예제 3
입력
```
4 5
3
2
2
2
3
1
2
1
2
```
예상 출력
```
55
```