21691_E-bookZealo

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 Figure1, ACM knows that how many books the zealot has read.

Figure 1

The zealot read only 1 book on day1 and read 5 books on day3. And from figure2, ACM knows the cost of reading one e-Book. Unfortunately, the cost varies instead of being constant.

Figure 2

The cost of Day1 and Day2 is 5 per e-Book, and it changed to 1 per e-Book on Day3, and it changed to 2 per e-Book on Day5. Therefore, the zealot should pay  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 the figure 3 below.

Figure 3

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 books by Set Menu A2, and pays last 5 without any set menus, he'll pay . 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 figure4.

Figure 4

It means that if the zealot chooses the Set Menu B1, he will 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. 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.

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 d₁, d₂ … d_n ( ∑d_i ≤ 10,000), representing the number of books the zealot read on Day 1, Day 2, …, Day n. The third line contains only one integer n₁ (0 < n₁ ≤ 1,000), representing the number of different price. Then n₁ integer pairs follow in separated lines.

c₁  p₁
c₂  p₂
  …
c_n1  p_n1

(c₁ = 1, c₁ < c₂ < … < c_n1 ≤ n,  p₁, p₂ … p_n1 > 0)

It means that at c_i day, the price of reading one book changes to p_i (0 < i ≤ n₁). In the next line, one integer n₂ (0 ≤ n₂ ≤ 1,000), representing the number of set menu A (Books Set Menus, see the figure 3). Then n₂ integer pairs are in the following separated lines.

a₁  r₁
a₂  r₂
  …
a_n2  r_n2

(0 < a₁ < a₂ < … < a_n2 ≤ 10,000,   r₁, r₂ … r_n2 > 0)

It means that the zealot can pay r_i for reading a_i (or less a_i) consecutive books (0 < i ≤ n₂). Then one integer n₃ (0 ≤ n₃ ≤ 1,000) follows in then next line, representing the number of set menu B (Days Set Menus, see the figure 4). Then n₃ integer pairs are in the following separated lines.

b₁  s₁
b₂  s₂
  …
b_n3  s_n3

(0 < b₁ < b₂ < … < b_n3 ≤ 1,000,  s₁, s₂ … s_n3 > 0)

It means that the zealot can pay s_i for reading books of b_i (or less b_i) continued days (0 < i ≤ n₃  ).

The input is terminated by a line with one zero.

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

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

12