说明

算法提高&nbsp 促销购物&nbsp  
时间限制：1.0s&nbsp  &nbsp 内存限制：256.0MB
 &nbsp  &nbsp
问题描述
　　张超来到了超市购物。
　　每个物品都有价格，正好赶上商店推出促销方案。就是把许多东西一起买更便宜（保证优惠方案一定比原价便宜）。物品要买正好的个数，而且不能为了便宜而买不需要的物品。
　　张超拿到了优惠方案，和需要购买的物品清单，当然想求出最小的花费。他是信息学选手，自然地想到写个程序解决问题。
输入格式
　　第一行促销物品的种类数（0&nbsp < =&nbsp s&nbsp < =&nbsp 99）。
　　第二行..第s+1&nbsp 行每一行都用几个整数来表示一种促销方式。
　　第一个整数&nbsp n&nbsp （1&nbsp < =&nbsp n&nbsp < =&nbsp 5），表示这种优惠方式由&nbsp n&nbsp 种商品组成。
　　后面&nbsp n&nbsp 对整数&nbsp c&nbsp 和&nbsp k&nbsp 表示&nbsp k&nbsp （1&nbsp < =&nbsp k&nbsp < =&nbsp 5）个编号为&nbsp c&nbsp （1&nbsp < =&nbsp c&nbsp < =&nbsp 999）的商品共同构成这种方案。
　　最后的整数&nbsp p&nbsp 表示这种优惠的优惠价（1&nbsp < =&nbsp p&nbsp < =&nbsp 9999）。也就是把当前的方案中的物品全买需要的价格。
　　第&nbsp s+2&nbsp 行这行一个整数b&nbsp （0&nbsp < =&nbsp b&nbsp < =&nbsp 5），表示需要购买&nbsp b&nbsp 种不同的商品。
　　第&nbsp s+3&nbsp 行..第&nbsp s+b+2&nbsp 行这&nbsp b&nbsp 行中的每一行包括三个整数：c&nbsp ，k&nbsp ，和&nbsp p&nbsp 。
　　C&nbsp 表示唯一的商品编号（1&nbsp < =&nbsp c&nbsp < =&nbsp 999），
　　k&nbsp 表示需要购买的&nbsp c&nbsp 商品的数量（1&nbsp < =&nbsp k&nbsp < =&nbsp 5）。
　　p&nbsp 表示&nbsp c&nbsp 商品的原价（1&nbsp < =&nbsp p&nbsp < =&nbsp 999）。
　　最多购买&nbsp 5*5=25&nbsp 个商品。
输出格式
　　一个整数ans，表示需要花的最小费用
样例输入
2
1&nbsp 7&nbsp 3&nbsp 5
2&nbsp 7&nbsp 1&nbsp 8&nbsp 2&nbsp 10
2
7&nbsp 3&nbsp 2
8&nbsp 2&nbsp 5
样例输出
14