749. 电子书狂热者

【问题描述】

最低价值协会（ ACM ）是一个非营利性的组织，旨在帮助人们节省资源和金钱。现在， ACM 正在发展一种软件，帮助号称是电子书狂热者省钱。
电子书狂热者热衷于在线读书，有时他一天读的书超过 10 本，没人知道他一天休息多长时间，电子书不是免费的，事实上，他们并不便宜。通过下图（ 2.5.1 ）， ACM 能了解到狂热者读了多少本书。

图 2.5.1 所读的书

狂热者在第一天读了 1 本书，第三天读了 5 本书，通过图 2.5.2 ， ACM 能知道读一本电子书的价格，不幸的是，价格并不是一成不变的。

图 2.5.2 每天的价格

在第 1 天和第 2 天每本电子书的价格为 5 ，到第三天每本书的价格变为 1 ，在第 5 天每本书价格又变为 2 ，因此狂热者需要为他读过的 9 本书付给电子书经营者的钱数为： 5×(1+1)+1×(5+1)+2×1=18 。
为了吸引更多的人来在线读书，电子书经营者推出了一些套餐，见下图 (2.5.3) 。

图 2.5.3 菜单 A

这意味着如果狂热者选择套餐 A1 ，他连读两本书需付钱数为 6 ，如果选择套餐 A2 ，连读 4 本书需付钱数为 7 ，举例说明：如果他使用套餐 A1 为前两本书付费、用套餐 A2 为接下来的 4 本书付费，而剩下的 3 本书不使用任何套餐，那么所付总费用为： 6+7+1+1+2=17 。实际上，如果他使用套餐 A2 为前 4 本书付费，剩下的 5 本书不使用任何套餐，他将付的费用为： 7+1×3+1+2=13 。当然了，如果需要的话套餐可以多次使用，而且，如果需要，可以使用 “w 本书套餐 ” 为连续的 q 本书付费，其中 q(0 < q < w) 此外，电子书经营者还推出了另一类套餐，在这些套餐中，经营者关心的重点不在狂热者读了多少本书，而在于狂热者读了多少天书。请看下图 (2.5.4) ：

图 2.5.4 菜单 B

这意味着，如果狂热者选择套餐 B1 ，他将为连续三天的读书（不管读了多少本）付费用为 9 ，如果选择套餐 B2 ，连续读 4 天要付的费用为 12 。举例说明：如果他用套餐 B2 为前 4 天付费，剩下的一天不使用任何套餐，他所需付的费用为： 12+2=14 ，同样的，套餐不限使用次数，并且可以使用 “w 天套餐 ” 为连续的 q 天阅读付费，其中q (0 < q < w)

【输入格式】
输入文件中有若干个测试数据，对于每一组测试数据，第一行只包含一个整数 n(0≤n≤1,000) ，表示狂热者所读的天数。

第二行包含 n 个非负整数 d 1 ,d 2 ,...,d n （∑ d i ≤10,000)

然后是一个整数n1表示有n1次价格变化 (0 < n1 ≤ 1,000)

c 1 p 1
c 2 p 2
...
c n1 p n1
(c 1 =1 ， c1 < c2 < … < cn1 ≤ n, p1, p2… pn1 > 0)
这些数据表示在第 c i 天，读一本书的价格变为 pi (0 < i ≤ n1)

接着是一个整数n2,表示第一种套餐的数量 (0 ≤ n2 ≤ 1,000)

a 1 r 1
a 2 r 2
...
a n2 r n2

(0 < a1 < a2 < … < an2 ≤ 10,000, r1, r2… rn2 > 0)
这些数据表示狂热者可以为连续读的 a i （或小于 a i ）本书付费用 r i ，

接着是一个整数n3,表示第二种套餐的数量 (0 ≤ n3 ≤ 1,000)

b 1 s 1
b 2 s 2
...
b n3 s n3
(0 < b1 < b2 < … < bn3 ≤ 1,000, s1, s2… sn3 > 0)
这些数据表示狂热者可以为连续读的 b i （或小于 b i ）天付费用 s i ，

 输入数据以单独的一行包含一个 0 表示结束。
【输出格式】
对于每一个测试数据，输出仅有一行，即狂热者所需付的最小费用。
【输入样例】
输入文件名： zealot .in
5
1 1 5 1 1
3
1 5
3 1
5 2
2
2 6
4 7
2
3 9
4 12
0
输出文件名： zealot .out
12