시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 12 10 83.333%

문제

상근이네 자동차 공장에는 직원이 N명 있다. 이 공장은 자동차를 컨베이어 벨트에 올려놓고 차를 만든다. 직원은 1번부터 N번까지 번호가 매겨져 있다. 직원 1은 컨베이어 벨트의 가장 왼족에 있고, N은 오른쪽에 있다. 각 직원이 하는 일은 모두 다르다.

차 한 대를 만드려면, 직원 1(상근)이부터 작업을 시작한다. 상근이가 작업을 끝내면 직원 2가 작업을 시작하고, 직원 2가 작업을 끝내면 직원 3이 작업을 시작한다. 그리고 직원 N이 작업을 끝내면 그제야 차가 완성되는 것이다. 차 M대를 만드려면, 1부터 M번까지 순서대로 차를 만들어야 한다.

각 직원 i가 자신의 일을 끝내는데 필요한 시간은 Ti이다. 또, 각 자동차 j의 복잡도는 Fj이다. 직원 i가 자동차 j의 작업을 완료하는데 필요한 시간은 Ti*Fj가 된다.

어떤 직원이 자신의 작업을 끝낸다면, 그 차는 즉시 다음 직원에게 넘겨진다. 따라서, 그 때, 다음 직원이 일을 하고 있으면 안된다.

모든 일은 상근이가 시작한다. 상근이는 위와 같이 어떤 직원이 작업을 끝내고 다음 직원에게 차를 넘겼는데, 다음 직원이 일을 하고 있는 상황이 발생하지 않게 하려고 한다. 그렇게 하기 위해서 상근이는 작업을 하지 않고 기다려야 하는 시간이 있다. 이 때, 이 시간을 최소로 하려고 한다.

모든 직원이 자신의 일을 끝내는데 필요한 시간과 모든 자동차의 복잡도가 주어진다. 이 때, 차를 모두 만들기 위해서 필요한 시간을 구하는 프로그램을 작성하시오.

입력

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

다음 N개 줄에는 직원 i의 작업 시간 Ti가 주어진다.

다음 M개 줄에는 자동차 j의 복잡도 Fj가 주어진다.

1 ≤ Ti, Fj ≤ 10,000

출력

첫째 줄에 자동차를 모두 만들기 위해 필요한 최소 시간을 출력한다.

예제 입력

3 3
2
1
1
2
1
1

예제 출력

11

힌트

4분이 지나면, 직원 1이 첫 번째 차를 만드는 작업을 완료한다. 그리고 즉시 다음 직원에게 차를 넘긴다. 하지만, 바로 두 번째 차를 만드는 직업을 시작하면 안된다. 그 이유는 7분이 지난 후에, 두 번째 직원은 두 번째 차 작업을 끝냈지만, 세 번째 직원은 아직 첫 번째 차 작업을 끝내지 않았기 때문이다. 따라서, 상근이는 1분을 쉬고 5분이 지났을 때, 두 번째 차를 만들기 시작한다. 또, 세 번째 차는 7분이 지났을 때 시작한다. 첫 번째 차는 작업을 시작한지 8분이 지났을 때 완성되고, 두 번째 차는 9분, 세 번째 차는 11분이 지난 뒤에 완성된다. 따라서, 정답은 11이다.