Description

It will be the 50th anniversary of founding of UESTC soon. We, who live in the RX dormitory, ought to do something special to celebrate this great event. But what should we do? We decide to arrange a meeting in RX dormitory to talk about this thing. On the i-th floor, we will choose C(i) students to take part in the meeting. Unfortunately, the elevator does not work now! So it is hard to decide which floor should be chosen to be the meeting place. The reason is that we all hate climbing up or down. If the meeting is hold on the 12th floor, the one who lives 12th floor will be very glad, however, the one who lives on the first floor may be discontented. Now we ask you for help!
To make things clearer, we make some assumptions. If the one who is on the i-th floor must clime up j floors, his discontent will be j * U[i]. Similarly, if he must clime down j floors, his discontent will be j * D[i]. Your task is find a floor, if we hold the meeting on that floor, the sum of all participant's discontent will be minimum. You know that RX dormitory has only 12 floors, how about if the number of floors is huge? It is your time now :)

Input

Input starts with a integer n (1 <= n <= 50000), which is the number of floors.
The next n integers describe C(i) of each floor from 1-st to n-th floor.
Then n lines follows, each line contains two integers, U(i) and D(i). All integers except n are not negative and less than 100;

Output

Output is a single integer, the minimum discontent sum.

Sample Input

3
1 1 1
1 1
2 2
3 3

Sample Output

4

Source

UESTC 4th programming contest