시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 56 35 26 65.000%

문제

스타로드와 토끼는 토르를 구출하기 위해서 우주선을 만들고 있다.

우주선을 만들기 위해서는 총 N개의 부품을 상점에서 모두 구입해야 한다. 모든 부품은 무게 W와 에너지 E를 갖고 있다. 상점에서는 모든 부품을 1부터 N번까지 부품을 순서대로 나열해놓고 판매하고 있다. 

이 상점에서는 특이하게도 부품의 가격을 W*E의 비용으로 팔고 있다. 상점에서는 또한 특이한 방식의 판매를 하는데, L 부품부터 R 부품중 최대 무게 W_max 와 최대 에너지 E_max의 곱 W_max *E_max의 비용을 지불한다면 L부터 R사이의 모든 부품을 한번에 구입할 수 있다. 또한 이 상점은 X부품과 Y부품 (X<Y)을 동시에 구입하거나 X부품을 Y부품 보다 먼저 구입할 순 있지만, Y부품을 X부품보다 먼저 구입할 순 없다.

그렇다면 스타로드와 토끼가 모든 부품을 살 수 있는 최소의 비용을 구해보도록 하자.

입력

첫번째  줄에는 부품의 개수 N(1 ≤ N ≤ 1,000)가 주어진다. 

두번째 줄에는 각 부품의 무게 W(0 ≤ W ≤ 1,000,000)가 주어진다.

세번째 줄에는 각 부품의 에너지 E(0 ≤ E ≤ 1,000,000)가 주어진다.

출력

스타로드와 토끼가 모든 부품을 살 수 있는 최소비용을 한줄에 출력하라.

예제 입력 1

5
1 2 3 4 5
3 2 8 9 4

예제 출력 1

45

예제 입력 2

5
10 9 1 7 6
4 2 99 4 3

예제 출력 2

167

힌트

2번째 예제에서는  1,2번 부품을 10 x 4 의 비용으로 한번에 구입하고 3번 부품을 99의 비용으로 구입하고 4,5번 부품을 7x4의 비용으로 구입해서 총 167의 비용으로 구입한다면 최소의 비용으로 모든 부품을 구입할 수 있다.