주유소

어떤 나라에 도시 N개가 일직선 도로 위에 놓여 있다. 편의상 이 직선을 수평 방향으로 두자. 제일 왼쪽 도시에서 제일 오른쪽 도시까지 자동차로 이동하려고 한다. 인접한 두 도시를 잇는 도로는 길이가 서로 다를 수 있다. 길이의 단위는 km를 쓴다.

출발할 때 자동차에 기름이 없으므로 주유소에서 기름을 넣고 떠나야 한다. 기름통 크기는 무제한이라 얼마든지 많이 넣을 수 있다. 도로를 1km 달릴 때마다 기름 1리터를 쓴다. 각 도시에는 주유소가 하나씩 있고, 리터당 가격은 도시마다 다를 수 있다. 가격의 단위는 원을 쓴다.

예를 들어 아래 그림처럼 도시가 4개 있다고 하자. 원 안의 숫자는 그 도시 주유소의 리터당 가격이고, 도로 위의 숫자는 도로의 길이다.

제일 왼쪽 도시에서 기름 6리터를 넣고 더 주유하지 않은 채 제일 오른쪽 도시까지 가면 총비용은 30원이다. 제일 왼쪽 도시에서 2리터를 넣고(2 × 5 = 10원) 다음 도시로 이동한 뒤 3리터를 넣고(3 × 2 = 6원) 그다음 도시에서 1리터를 넣어(1 × 4 = 4원) 제일 오른쪽 도시로 가면 총비용은 20원이다. 제일 왼쪽 도시에서 2리터를 넣고(2 × 5 = 10원) 다음 도시로 이동한 뒤 4리터를 넣어(4 × 2 = 8원) 제일 오른쪽 도시까지 가면 총비용은 18원이다.

각 도시 주유소의 리터당 가격과 도시를 잇는 도로의 길이를 입력받아 제일 왼쪽 도시에서 제일 오른쪽 도시까지 이동하는 최소 비용을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 N이 주어진다. (2 ≤ N ≤ 100,000)

둘째 줄에 인접한 두 도시를 잇는 도로의 길이가 제일 왼쪽 도로부터 차례대로 N-1개의 자연수로 주어진다.

셋째 줄에 주유소의 리터당 가격이 제일 왼쪽 도시부터 차례대로 N개의 자연수로 주어진다.

제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1 이상 1,000,000,000 이하의 자연수다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수다.

제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 한 줄에 출력한다.