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. 



It means if the zealot chooses Set Menu A1, he will pay 6 for reading 2 consecutive books; and if he chooses Set Menu A2, he will pay 7 for reading 4 consecutive books. For example, if he pays the first 2 books by Set Menu A1, and pays the next 4 books by Set Menu A2, then pays the last 3 books without any set menus, he'll pay 6+7+1+1+2=17. In fact, if he pays the first 4 course, the Set Menu A2, and pays last 5 without any set menus, he'll pay 7+1*3+1+2=13. Of course, the Set Menu can be used any times if necessary. And if necessary, the w-books Set Menu can use to pay q(0 < q < w) book(s); for example, the zealot can pay 7 for 3 continued books by Set Menu A2(3 < 4).

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.

It means that if the zealot chooses the Set Menu B1, he wil pay 9 for reading any number books within 3 consecutive days; and if he chooses Set Menu B2, he will pay 12 for reading books of 4 continued days. For example, if he pays first 4 days reading by Set Menu B2, and pays last day reading without any set menus, he'll pay 12+2=14. Similarly, the set menus can be used any times. And the w-days Set Menu can use to pay q(0 < q < w) day(s) reading.

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

Hint

 

Source

ZSCPC9