cho.sh

Gas Stations

Given road lengths and per-city fuel prices on a line, buy fuel along the way to minimize the total cost of driving from the first city to the last.

Medium5GreedyArrayImplementationMathInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

A country has N cities standing on one straight road. Put that straight line horizontally. You want to drive a car from the leftmost city to the rightmost city. The roads between adjacent cities can have different lengths. Lengths are given in km.

The car has no fuel when you start, so you have to buy fuel at a gas station before leaving. The tank has unlimited capacity, so you can buy as much fuel as you want. Driving 1 km burns 1 liter of fuel. Each city has exactly one gas station, and the price per liter can differ from city to city. Prices are given in won.

For example, suppose the country has 4 cities as in the picture below. The number inside a circle is the price per liter at that city's gas station. The number above a road is the length of that road.

If you buy 6 liters at the leftmost city and drive to the rightmost city without buying again, the total cost is 30 won. If you buy 2 liters at the leftmost city (2 × 5 = 10 won), drive to the next city and buy 3 liters (3 × 2 = 6 won), then buy 1 liter at the city after that (1 × 4 = 4 won) and drive to the rightmost city, the total cost is 20 won. If you buy 2 liters at the leftmost city (2 × 5 = 10 won), drive to the next city and buy 4 liters (4 × 2 = 8 won), then drive to the rightmost city, the total cost is 18 won.

Write a program that reads the price per liter at every gas station and the length of every road, then computes the minimum cost of driving from the leftmost city to the rightmost city.

Input

The first line contains the number of cities N. (2 ≤ N ≤ 100,000)

The second line contains N-1 natural numbers, the lengths of the roads joining adjacent cities, listed from the leftmost road.

The third line contains N natural numbers, the price per liter at each gas station, listed from the leftmost city.

The distance from the leftmost city to the rightmost city is a natural number between 1 and 1,000,000,000. Each price per liter is a natural number between 1 and 1,000,000,000.

Output

Print the minimum cost of driving from the leftmost city to the rightmost city on one line.