Loading [MathJax]/jax/output/HTML-CSS/jax.js
编程题
                装饰珠

题目描述

在怪物猎人这一款游戏中,玩家可以通过给装备镶嵌不同的装饰珠来获取 相应的技能,以提升自己的战斗能力。

已知猎人身上一共有 6 件装备,每件装备可能有若干个装饰孔,每个装饰孔有各自的等级,可以镶嵌一颗小于等于自身等级的装饰珠 (也可以选择不镶嵌)。

装饰珠有 M 种,编号 1 至 M,分别对应 M 种技能,第 i 种装饰珠的等级为 Li,只能镶嵌在等级大于等于 Li 的装饰孔中。

对第 i 种技能来说,当装备相应技能的装饰珠数量达到 Ki 个时,会产生 Wi(Ki) 的价值。镶嵌同类技能的数量越多,产生的价值越大,即 Wi(Ki1)<Wi(Ki)。但每个技能都有上限 Pi(1Pi7),当装备的珠子数量超过 Pi 时,只会产生 Wi(Pi) 的价值。

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

输入描述

输入的第 1 至 6 行,包含 6 件装备的描述。其中第 i 行的第一个整数 Ni 表示第 i 件装备的装饰孔数量。后面紧接着 Ni 个整数,分别表示该装备上每个装饰孔的等级 L (1L4)

第 7 行包含一个正整数 M,表示装饰珠 (技能) 种类数量。

第 8 至 M + 7 行,每行描述一种装饰珠 (技能) 的情况。每行的前两个整数 Lj (1Lj4)Pj (1Pi7) 分别表示第 j 种装饰珠的等级和上限。接下来 Pj 个整数,其中第 k 个数表示该装备中装饰珠数量为 k 时的价值 Wj(k)

其中,1Ni50,1M104,1Wj(k)104

输出描述

输出一行包含一个整数,表示能够得到的最大价值。

输入输出样例

示例

>输入

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

>样例说明

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

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

查看答案
赣ICP备20007335号-2