游戏中的每个项目都有一个等级。等级越高,物品的基础参数越高。我们只考虑以下基本参数:攻击(atk)、防御(def)和对不同类型冲击的抵抗力(res)。
每个项目属于一个类别。在这个问题中,我们将只考虑其中的三个类别:武器、盔甲、球体。
此外,每件物品中都隐藏着一个全新的世界。我们可以通过前往其世界来提高物品的等级。我们还可以捕捉物品世界中的所谓居民
居民是生活在物品内部的生物。每个居民都会为其当前所在的项目提供一些奖励。我们只会考虑以下类型的居民:角斗士(提高物品的攻击力)、哨兵(提高防御力)和医生(提高抵抗力)。
每个项目都有尺寸参数。该参数限制了一个项目内可以居住的最大居民数量。我们可以在项目之间移动居民。在某一时刻,我们可以从一个项目中取出一些居民,并将其移动到其他项目(如果该项目有可供新居民使用的空闲位置)。我们不能将居民从物品中移走并留在外面——任何时候他们都应该在某个物品内。
拉哈尔拥有一定数量的物品。他想在物品之间移动居民,以便为自己装备武器、盔甲和防御球。武器的攻击力最终应该是最大的。在所有包含武器最大攻击参数的装备样式中,我们应该选择盔甲防御参数最大的装备样式。在所有这些装备模式中,我们应该选择防御球具有尽可能最大的 res 参数的一种。武器的 def 和 res、盔甲的 atk 和 res 以及球体的 atk 和 def 参数的值对于拉哈尔来说是无关紧要的。
找出拉哈尔可以获得的最佳装备图案。
输入
第一行包含数字 n (3 ≤ n ≤ 100) — 表示 Laharl 有多少个物品。
然后跟随n行。每一行包含一个项目的描述。描述的形式如下:“name class atk def res size”——物品的名称、等级、基本攻击、防御和抵抗参数及其相应的大小。
- name 和 class 是字符串,atk、def、res 和 size 是整数。
- 名称由小写拉丁字母组成,长度范围为 1 到 10(含)。
- 类别可以是“武器”、“盔甲”或“球体”。
- 0 ≤ atk, def, res ≤ 1000。
- 1 ≤ 尺寸 ≤ 10。
保证拉哈尔每个职业至少拥有一件物品。
下一行包含一个整数 k (1 ≤ k ≤ 1000) — 居民数量。
接下来是 k 行。他们每个人都描述了一位居民。居民描述如下:“姓名类型奖励家庭”——居民的姓名、类型、居民为项目的相应参数添加的点数以及当前包含居民的项目的名称。
- 名称、类型和家庭是字符串,奖金是整数。
- 名称由小写拉丁字母组成,长度范围为 1 到 10(含)。
- 类型可以是“角斗士”、“哨兵”或“医生”。
- 1 ≤ 奖金 ≤ 100。
保证每个项目中的居民数量不超过该项目的大小。
所有物品和居民的名称都是两两不同的。
输入中的所有单词和数字均以单个空格分隔。
输出
第一行打印最佳装备图案中的武器名称;然后打印武器包含的居民数量;然后打印居民的姓名。
以相同的形式在第二行和第三行打印盔甲和防御球的名称以及它们所包含的居民。
使用单个空格进行分隔。
如果有多种可能的解决方案,请打印其中任何一个。
示例
输入 #1
4 sword weapon 10 2 3 2 pagstarmor armor 0 15 3 1 iceorb orb 3 2 13 2 longbow weapon 9 1 2 1 5 mike gladiator 5 longbow bobby sentry 6 pagstarmor petr gladiator 7 iceorb teddy physician 6 sword blackjack sentry 8 sword
输出 #1
sword 2 petr mike pagstarmor 1 blackjack iceorb 2 teddy bobby
输入 #2
4 sword weapon 10 2 3 2 pagstarmor armor 0 15 3 1 iceorb orb 3 2 13 2 longbow weapon 9 1 2 1 6 mike gladiator 5 longbow bobby sentry 6 pagstarmor petr gladiator 7 iceorb teddy physician 6 sword blackjack sentry 8 sword joe physician 6 iceorb
输出 #2
longbow 1 mike pagstarmor 1 bobby iceorb 2 petr joe
注意
在第二个样本中,我们的物品内部没有可用空间,因此我们无法在物品之间移动居民。