已知猎人身上一共有 6件装备，每件装备可能有若干个装饰孔，每个装饰孔有各自的等级，可以镶嵌一颗小于等于自身等级的装饰珠(也可以选择不镶嵌)。装饰珠有M种，编号1至M，分别对应M种技能，第i种装饰珠的等级为 Li，只能镶嵌在等级大于等于 Li的装饰孔中。

对第 i种技能来说，当装备相应技能的装饰珠数量达到 Ki个时，会产生 Wi(Ki)

 的价值。镶嵌同类技能的数量越多，产生的价值越大，即 Wi(Ki−1)<Wi(Ki)。但每个技能都有上限 Pi(1≤Pi≤7)，当装备的珠子数量超过 Pi时，只会产生 Wi(Pi)的价值。

对于给定的装备和装饰珠数据，求解如何镶嵌装饰珠，使得 6件装备能得到的总价值达到最大。

1 1
2 1 2
1 1
2 2 2
1 1
1 3
3
1 5 1 2 3 5 8
2 4 2 4 8 15
3 2 5 10

20

样例说明：

按照如下方式镶嵌珠子得到最大价值 20，括号内表示镶嵌的装饰珠的种类编号：

1: (1)
2: (1) (2)
3: (1)
4: (2) (2)
5: (1)
6: (2)

4颗技能 1装饰珠，4颗技能2装饰珠 W1(4)+W2(4)=5+15=20。

【评测用例规模与约定】

对于30的评测用例，1≤Ni≤10, 1≤M≤20, 1≤Wj(k)≤500；对于所有评测用例，1≤Ni≤50, 1≤M≤10000, 1≤Wj(k)≤10000。