4070. 夏娜的菠萝包

【题目描述】

夏娜很喜欢吃菠萝包，她的经纪人RC每半个月就要为她安排接下来的菠萝包计划。今天是7月初，RC又要去商场买菠萝包了。

   这次RC总共买了N种菠萝包，每种一个。每个菠萝包都有一个初始美味值T，每过一天就会减少Di，即第2天美味值为Ti-Di，第3天为Ti-2*Di，依此类推。一旦美味值减为负数，那个包就坏掉不能吃了。

   RC每天都要为夏娜安排当天吃菠萝包的组合，这些组合不是随意的，而是只能从夏娜喜欢的M种搭配中挑选一种。每种搭配是由Ki个菠萝包组成的，一种搭配的总美味值是这Ki个菠萝包当天的美味值之和再加上一个额外的搭配美味值Ei。不过要注意，一旦某种搭配的其中一个菠萝包坏掉了，这个搭配就不能选用了；而且，有可能存在两个搭配，里面的组合是一样的，但额外的搭配美味值却不同。

   RC想让可爱的小夏娜尽可能地吃得美味，因此希望能找出一种最优的方案，让小夏娜吃上若干天的菠萝包，这些天的美味值之和最大。

   但Rc面对着两个对手，一个叫bug，另一个叫zzy，他们也想得到这个经纪人之位，因此如果他们提出更优的方案，RC就可能失去他的小夏娜了。那么，你能帮帮RC吗?

【输入格式】

输入文件包含多组数据。

每组数据的第1行为一个正整数N，表示菠萝包的种数，按1～N编号。

接下来N行，每行两个正整数Ti(Ti<100)和Di(Di<l00)，表示第i种菠萝包的初始美味值和每天递减值。

第N+2行为一个正整数M，表示搭配的种数。

接下来M行，每行先是一个正整数Ki，表示组成这个搭配的菠萝包数目，然后是一个非负整数Ei(Ei<100)，表示这种搭配额外的美味值，最后是Ki个整数，每个整数为菠萝包的编号。

当N=O时表示输入结束。

【输出格式】

对于每组输入数据输出一行，仅包含一个整数，表示最大的美味值之和。

【样例输入】

2
3 1
4 2
2
1 1 1
1 1 2
2
3 1
4 2
3
1 1 1
1 1 2
2 2 1 2
0

【样例输出】

8
9

【提示】

样例说明

 对于第一个样例，只有两个方案：

 (1)第一天选择搭配1，即吃编号1的菠萝包，美味值为3+1=4；第二天选择搭配2，即吃编号2的菠萝包，美味值为2+1=3。此时已把菠萝包都吃完了，美味值总和为4+3=7。

 (2)第一天选择搭配2，即吃编号2的菠萝包，美昧值为4+1=5；第二天选择搭配1，即吃编号1的菠萝包，美味值为2+1=3，此时已把菠萝包都吃完了，美味值总和为5+3=8。

 因此，第2个方案为最优方案，最大美味值总和为8。

对于第二个样例，除了上述两个方案，还有第3个方案：

(3)第一天选择搭配3，即编号为l和2的菠萝包一起吃，美味值为3+4+2=9。此时已把菠萝包都吃完了，美味值总和即为9。

   虽然第3个方案只能吃1天，但因为其美昧值总和最大，所以选择第3个方案，答案为9。

输入输出说明

   对于30％的数据，N≤8，M≤10。

   对于60％的数据，N≤11，M≤15。

   对于100％的数据，N≤14，M≤20。

大样例

【来源】

在此键入。