Star Trek

The United Federation of Planets (abbreviated UFP) is an interstellar union of planetary governments made up of n planets. All planets are numbered from 1 to n. The headquarters of UFP is on planet 1. UFP has built a straight interstellar route that connects planet 1 to planet n in sequence.

The spaceships developed for interstellar travel have nearly unlimited energy, so a ship can move along the route between two planets without stopping. Each planet has its own spaceship model. The spaceships perform about the same, but their speeds differ by model. A spaceship's pace is given as the number of hours needed to travel one light-year. A light-year is a unit of distance used for astronomical distances. If a ship's pace is 10, it takes 10 hours to travel one light-year.

You live on planet 1 and are about to travel to planet n. To reach planet n as quickly as possible, you may transfer to spaceships on other planets along the way. Keep in mind that such a transfer needs extra time to prepare for landing, takeoff, entry and departure formalities, and so on.

For example, suppose UFP has five planets, with the distances between adjacent planets, the spaceship paces, and the preparation times given as in the figure below.

If a spaceship on planet 1 moves directly to planet 5, it takes 165 hours (= 3 + 27 × 6). If you transfer on planet 2, it takes 107 hours (= 3 + 5 × 6 + 8 + 22 × 3). If you transfer on planet 2 and then on planet 4, it takes 130 hours (= 3 + 5 × 6 + 8 + 14 × 3 + 15 + 8 × 4). Considering every possible travel plan, the minimum time to reach planet 5 is 107 hours.

Given the planet and spaceship information of UFP, write a program to find the minimum time to travel from planet 1 to planet n.

Your program reads from standard input. The first line of input contains an integer, n (3 ≤ n ≤ 100,000), the number of planets of UFP. The planets are numbered from 1 to n. The next line contains n − 1 integers, where the i-th integer is the distance between planet i and planet i + 1. All distances are between 1 and 1,000. The following n − 1 lines each contain two integers, p and s (0 ≤ p ≤ 109, 1 ≤ s ≤ 105), where p is the preparation time and s is the spaceship's pace of planet i.

Your program writes to standard output. Print exactly one line. The line should contain an integer, the minimum time to travel from planet 1 to planet n.