Vova bought a new wideangle lens for his camera a few days ago. Now he wants to take a
panoramic photo with this lens, and that is the reason why he decided to climb the nearest hill.
There is a single narrow serpentine path leading from base of the hill to its top.
Vova introduced coordinate axes in such a way that OY is directed along the hill side from
base to top and OX is orthogonal to it. The path is represented as a polyline with n segments,
vertices of which follow in the order of strictly increasing ycoordinate. For each segment of the path, Vova knows the
time required to change xcoordinate by one while moving along this segment.
Moreover, Vova can use cableways. They start at some point of the path, run strictly up the hill parallel to OY axis and end at the
next intersection with the path. Vova knows the time required to use each cableway.
Help Vova climb the hill before it gets dark! Note that Vova is so
determined that he will refuse to go down the hill even if this action helps him to
climb the hill faster.
Input
The first line contains a number of segments in the path n (1 ≤ n ≤ 10^{5}).
The next line contains n + 1 integers which are xcoordinates of polyline vertices in the order from
base to top. No two consecutive vertices have the same xcoordinate.
The ith of the following n lines contains integers v_{i} and m_{i} which are time required to change xcoordinate by one
while moving along the ith segment and a number of cableways starting at the ith segment, respectively. The rest of this line
contains m_{i} pairs of integers describing the cableways. Each cableway is described with xcoordinate of its start point and
time required to use this cableway. The cableways are described in the order from base to top. No two cableways start
at the same point. If a cableway starts at the common point of two path segments, it encounters in the description of only one segment.
It is guaranteed that each cableway ends somewhere on the path.
All numbers in lines are separated by spaces. All coordinates don't exceed 10^{6} in their absolute value.
All times are positive and don't exceed 10^{6}. The total number of cableways doesn't exceed 10^{5}.
Output
Output the minimal time required to climb the hill.
Samples
input  output 

4
0 5 15 10 0
1 1 1 100
1 1 7 1
1 0
1 0
 15

3
0 10 0 10
10 0
10 1 10 1
10 0
 101

Problem Author: Denis Dublennykh
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2010