### Contest02-5 E-book Zealot

Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem Description

Association for Cost Minimum(ACM) is a non-profit organization which is engaged in helping people to save resource and money. Now, ACM wants to develop a kind of software to help so-called e-Book zealot to save money.

The e-Book zealot enjoys reading book on-line very much; sometimes he reads more than 10 books a day, nobody knows how long he sleeps a day. The e-Books are not free of charge. In fact, they're not cheap. From Figure 1, ACM knows that how many books the zealot has read. The zealot read only 1 book on Day1 and read 5 books on Day3. And from Figure 2, ACM knows the cost of reading one e-Book. Unfortunately, the cost varies instead of being constant. The cost of Day 1 and Day 2 is 5 per e-Book, and it changed to 1 per e-Book on Day 3, and it changed to 2 per e-Book on Day 5. Therefore, the zealot should pay 5*(1+1)+1*(5+1)+2*1=18 to the e-Book provider for the 9 books he read.

In order to attract more people to read on-line, the e-Book provider promotes some set-menus. See Figure 3 below. Further more, the e-Book provider promotes another kind of set-menus. In these set-menus, the provider doesn't care about the number of the books the zealot  reads; he cares about how many days the zealot reads. See Figure 4. Now, your task is to write a program to help the zealot. Help him to minimize the money he should pay according to the number of books he reads, the prices and the set menus.

#### Input

The input consists of several test cases. The first line of each test case contains only one integer n(0 < n <= 1,000), representing the number of days the zealot has read. The second line contains n non-negative integers d1,d2,...,dn
(∑di <= 10,000), representing the number of books the zealot read on Day 1,Day 2, ...,Day n. The third line contains
0 < i <= n
only one integer n1(0 < n1 <= 1,000), representing the number of different price. Then n1 integer pairs follow in separated lines.
c1 p1
c2 p2
...
cn1 pn1
(c1 = 1,c1 < c2 < ... < cn1 <= n, p1,p2,...,pn1 > 0)
It means that at ci day,the price of reading one book changes to pi(0 < i <= n1). In the next line, one integer n2(0 <= n2 <= 1,000), representing the number of set menu A(Books Set Menus, see the Figure 3). Then n2 integer pairs are in the following separated lines.
a1 r1
a2 r2
...
an2 rn2
(0 < a1 < a2 < ... < an2 <= 10,000, r1,r2,...,rn2 > 0)
It means that the zealot can pay ri for reading ai(or less ai) consecutive books(0 < i <= n2). Then one integer n3(0 <= n3 <= 1,000) follows in then next line, representing the number of set menu B(Days Set Menus, see the Figure 4). Then n3 integer pairs are in the following separated lines.
b1 s1
b2 s2
...
bn3 sn3
(0 < b1 < b2 < ... < bn3 <= 1,000, s1,s2,...,sn3 > 0)
It means that the zealot can pay si for reading books of bi(or less bi) continued days(0 < i <= n3).
The input is terminated by a line with one zero.

#### Output

For each test case, output only one single line contains the least money the zealot should pay.

#### Sample Input

5
1 1 5 1 1
3
1 5
3 1
5 2
2
2 6
4 7
2
3 9
4 12
0

#### Sample Output

12

ZSCPC9