2094: 促销购物

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