우주선 만들기
면접 대비시간 제한2초메모리 제한512 MB
순서대로 놓인 부품을 연속한 구간으로 나누어 사는데, 각 구간의 최대 무게와 최대 에너지의 곱을 낸다. 전체 비용의 최솟값을 구한다.
문제
스타로드와 토끼는 토르를 구출하기 위해 우주선을 만들고 있다.
우주선을 만들려면 총 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)가 주어진다.
출력
스타로드와 토끼가 모든 부품을 살 수 있는 최소 비용을 한 줄에 출력하라.
힌트
2번째 예제에서는 1, 2번 부품을 10 x 4의 비용으로 한 번에 사고, 3번 부품을 99의 비용으로 사고, 4, 5번 부품을 7x4의 비용으로 사면 총 167의 비용으로 모든 부품을 살 수 있다.