미코의 공장에는 N 명의 종업원이 있다. 컨베이어 벨트를 이용해서 차를 조립하고 있다.

가장 왼쪽에 있는 사람이 1 번이고 가장 오른쪽에 있는 사람이 N 번이다. 종업원의 각각은 정해진 작업을 하고 이 일을 마치기 위해 정해진 시간이 필요하다.

1 번 작업에 미코가 있다. 이 작업을 한 후에 2 번 종업원이 이 일을 받아서 마친 후 3 번 으로 ... N 번째 직원이 작업을 마친 후 이 차는 완성된다.

미코와 직원들은 M 대의 차를 생산해야 한다. 그리고 1 에서 M 순으로 이들을 생산해야 한다. i 번째 종업원은 일을 마치기 위해 Ti 만큼의 시간이 필요하다.

또한 차들은 조립 복잡도 Fj 가 필요하다. i 번째 직원이 j 번째 차의 일을 마치는데 필요한 시간은 Ti*Fj 이다.

종업원이 일을 마친 후 일을 넘겨 줄 때는 이 일을 받는 사람은 어떤 일도 하지 않아야 한다. 즉 일을 넘겨 줄 때 다른 차를 작업하지 않고 자유로워야 한다. 이런 시간과 요소가 주어질 때 이 조건을 만족하면서 모든 카를 조립하는데 필요한 최소 전체 시간을 계산하는 프로그램을 작성하라.

예를 들어 3 명, 3 대가 있다면

3 3
2
1
1
2
1
1

첫 차를 첫 번째 종업원이 끝내 후 다음 작업을 즉시 할 수 있지만 이렇게 하는 경우 7 시간 후 두 번째 사람이 세 번째 차를 세 번째 종원원에게 넘길 경우 아직 첫 번째 차를 작업 하고 있으므로 조건에 위배 된다. 그래서 두 번째 차는 5 분 후에 세 번째는 7 분 후에 작업을 하면 첫 번째 차는 8 분 후 , 두 번째 차는 9 분 , 세번째 차는 11 분 후에 작업을 끝낼 수 있으므로 총 시간은 11 이다.

Production of a single car starts with worker #1 (Mirko). After he had finished with his part of the job, worker #2 takes over, after him #3... When worker #N finishes with his part, the car is finished. Mirko and his workers have to produce M cars and they must produce them in order 1 to M. For every worker i we know Ti - time required for him to do his part of the job. For every car j we

know factor of assembly complexity Fj . Time in minutes for worker i to finish his part of he job on the car j is computed as a product TiFj .

After some worker has finished working on a car, he has to give it to the next worker instantly, without any delay (weird company policy). For that reason, the worker receiving the car has to be free (he must not be working on some other car). In order to fulfill this condition, Mirko has to choose a good timing to start building a new car. To be efficient, he’ll wait minimum number of minutes until he is certain that all of the conditions described are met.

Write a program which will, given worker times and factors of complexity for each car, compute total time required for producing all of the cars.

입력

i-th of the following N lines contains worker time Ti for the worker i.

j-th of the following M lines contains factor of complexity Fj for the car j.

These conditions hold: 1 ≤ Ti ≤ 10 000, 1 ≤ Fj ≤ 10 000.

출력

입출력 예

input

3 3
2
1
1
2
1
1

output

11

input

3 3
2
3
3
2
1
2

output

29

input

4 5
3
2
2
2
3
1
2
1
2

output

55

First sample description: After four minutes, first worker finishes working on the first car. He might 
start working on the second car immediately, but that would violate a condition that cars have to be 
passed to next workers as soon as they’re done (after seven minutes second worker would finish 
working on his part of second car, but the third worker would not be free to take over as he would still 
be working on the first car). That is the reason production of the second car is started after five 
minutes. Production of the third car starts after seven minutes. First car is finished after eight, second 
after nine and third after eleven seconds. Total time is then 11. 

출처:coci