Execution Time

Consider a system of n computers that carries out a certain task. The system works as follows.

1. The computers are numbered 1 through n. Each computer has its own rank and operating speed. Both the rank and the operating speed are positive integers.
2. The transmission time between computer i and computer j is (i - j)2.
3. The ranks of the n computers are c1, c2, … cn. (1 ≤ c1 ≤ c2 ≤ … ≤ cn ≤ n). When the given ranks are sorted in increasing order, | cj -cj-1 |≤ 1.
4. Every computer except those of the lowest rank can start operating only after it has received information from every computer of the rank one step below its own. At this point, starting to operate takes an amount of time equal to that computer's operating speed.
5. A computer of the lowest rank has no information to receive. It therefore starts operating as soon as the system starts up.
6. When a computer of rank c finishes operating, it sends information to every computer of rank c+1 and then terminates.
7. The system's task is complete when every computer has finished operating and terminated.
8. The lowest rank is 1.

Given information about this system, find the time it takes for the task to finish.

The first line gives the number of computers n. (3 ≤ n ≤ 100) The next n lines give the rank and operating speed t of each computer 1 through n, separated by a space. (1 ≤ t ≤ 100)

Print the answer to the problem.