在怪物猎人这一款游戏中,玩家可以通过给装备镶嵌不同的装饰珠来获取相应的技能,以提升自己的战斗能力。
已知猎人身上一共有6件装备,每件装备可能有若干个装饰孔,每个装饰孔有各自的等级,可以镶嵌一颗小于等于自身等级的装饰珠(也可以选择不镶嵌)。
装饰珠有M种,编号1至M,分别对应M 种技能,第i种装饰珠的等级为Li,只能镶嵌在等级大于等于Li的装饰孔中。
对第i种技能来说,当装备相应技能的装饰珠数量达到Ki 个时,会产生Wi(Ki) 的价值。镶嵌同类技能的数量越多,产生的价值越大,即Wi(Ki1)<Wi(Ki) 。但每个技能都有上限Pi(1<=Pi<=7) ,当装备的珠子数量超过Pi时,只会产生Wi(Pi)的价值。
对于给定的装备和装饰珠数据,求解如何镶嵌装饰珠,使得6件装备能得到的总价值达到最大。
输入的第1至6行,包含6件装备的描述。其中第i的第一个整数Ni表示第i 件装备的装饰孔数量。后面紧接着Ni个整数,分别表示该装备上每个装饰孔的等级L(1<=L<=4) 。
第7行包含一个正整数M,表示装饰珠(技能)种类数量。
第8至M+7行,每行描述一种装饰珠(技能)的情况。每行的前两个整数Lj(1<=Lj<=4)和Pj(1<=Pj<=7)分别表示第j 种装饰珠的等级和上限。接下来Pj个整数,其中第k个数表示装备该中装饰珠数量为k时的价值Wj(k)。
输出一行包含一个整数,表示能够得到的最大价值。
对于30%的评测用例,1<=Ni<=10,1<=M<=20,1<=Wj(k)<=500
对于所有评测用例,1<=Ni<=50,1<=M<=10000,1<=Wj(k)<=10000