Item World

题意翻译

### 题目描述 游戏里，每个物品都有一个等级。等级越高，物品的基础数值就越高。我们在本题中只考虑物品的攻击力(atk)，防御力(def)和魔法值(res)。 每件物品都属于一下三种之一：武器，防具和宝具。 每件物品中都藏着一个小小的世界。你在进入这些世界时可以为物品增加等级。我们还可以去抓这些世界中的居民。 居民就是物品世界中居住的生物。每个居民哦都会给当前所在的物品加点BUFF。居民有以下三种：能增加物品atk的斗士，能增加物品def的侍卫，以及能增加物品res的法师。 每一件物品都有一个容量。容量代表着能生活在这件物品中的最大居民数量。我们可以让居民在不同物品中跑来跑去。在一个时刻内我们可以在一件物品中取出若干个居民，并分散至若干个别的容量还没满的物品中。我们不可以把居民扔到物品外面，在任意时刻中居民都需要生存在物品中。 Laharl有一些物品。他想在挪动一些居民后装备上一件武器、一件防具和一件宝具。在Laharl挪动居民后，应该使他装备的武器的atk值最大。在满足以上条件的前提下，要尽量使他装备的武器的def值最大。在满足以上两个条件的前提下，要尽量使他装备的宝具的res值最大。 请你找到最佳的装备方案。 ### 输入格式 第一行包含一个整数$n\ (3 \leq n \leq 100)$，代表Laharl的物品数。 接下来有$n$行，每一行描述一件装备，形为两个字符串和四个数："$name\ class\ atk\ def\ res\ size$"，分别代表物品的名称，物品的种类，物品的攻击力，物品的防御力，物品的魔法值和物品的容量。 - $name$是个字符串，代表物品的名称。$1\leq|name|\leq10$，且$name$中只包含小写字母。 - $class$是个字符串，可以是"weapon"(武器)，"armor"(防具)，"orb"(宝具)。 - $0\leq atk, def, res \leq 1000$ - $1\leq size \leq 10$ 下一行包含一个整数$k\ (1\leq k \leq 1000)$，代表居民的个数。 接下来有$k$行，每一行描述一个居民，形为三个字符串和一个数："$name\ type\ bonus\ home$"。 - $name$是个字符串，代表居民的名字。$1\leq|name|\leq10$，且$name$中只包含小写字母。 - $type$是个字符串，可以是"gladiator"(斗士)，"sentry"(侍卫)，"physician"(法师)。 - $1\leq bonus \leq 100$ 保证每件物品初始时里面的居民数不超过物品的容量。 所有物品名和人名均是唯一的。 输入中所有字符串和整数都由一个空格隔开。 ### 输出格式 第一行，输出选中武器的名字，在挪动居民后选中武器中的居民数，和居民的名字。 第二行输出防具，第三行输出宝具，格式同上。 若有多组解，输出任意一组即可。

题目描述

Each item in the game has a level. The higher the level is, the higher basic parameters the item has. We shall consider only the following basic parameters: attack (atk), defense (def) and resistance to different types of impact (res). Each item belongs to one class. In this problem we will only consider three of such classes: weapon, armor, orb. Besides, there's a whole new world hidden inside each item. We can increase an item's level travelling to its world. We can also capture the so-called residents in the Item World Residents are the creatures that live inside items. Each resident gives some bonus to the item in which it is currently located. We will only consider residents of types: gladiator (who improves the item's atk), sentry (who improves def) and physician (who improves res). Each item has the size parameter. The parameter limits the maximum number of residents that can live inside an item. We can move residents between items. Within one moment of time we can take some resident from an item and move it to some other item if it has a free place for a new resident. We cannot remove a resident from the items and leave outside — any of them should be inside of some item at any moment of time. Laharl has a certain number of items. He wants to move the residents between items so as to equip himself with weapon, armor and a defensive orb. The weapon's atk should be largest possible in the end. Among all equipping patterns containing weapon's maximum atk parameter we should choose the ones where the armor’s def parameter is the largest possible. Among all such equipment patterns we should choose the one where the defensive orb would have the largest possible res parameter. Values of the parameters def and res of weapon, atk and res of armor and atk and def of orb are indifferent for Laharl. Find the optimal equipment pattern Laharl can get.

输入输出格式

输入格式

The first line contains number $ n $ ( $ 3<=n<=100 $ ) — representing how many items Laharl has. Then follow $ n $ lines. Each line contains description of an item. The description has the following form: " $ name $ $ class $ $ atk $ $ def $ $ res $ $ size $ " — the item's name, class, basic attack, defense and resistance parameters and its size correspondingly. - $ name $ and $ class $ are strings and $ atk $ , $ def $ , $ res $ and $ size $ are integers. - $ name $ consists of lowercase Latin letters and its length can range from $ 1 $ to $ 10 $ , inclusive. - $ class $ can be "weapon", "armor" or "orb". - $ 0<=atk,def,res<=1000 $ . - $ 1<=size<=10 $ . It is guaranteed that Laharl has at least one item of each class. The next line contains an integer $ k $ ( $ 1<=k<=1000 $ ) — the number of residents. Then $ k $ lines follow. Each of them describes a resident. A resident description looks like: " $ name $ $ type $ $ bonus $ $ home $ " — the resident's name, his type, the number of points the resident adds to the item's corresponding parameter and the name of the item which currently contains the resident. - $ name $ , $ type $ and $ home $ are strings and $ bonus $ is an integer. - $ name $ consists of lowercase Latin letters and its length can range from $ 1 $ to $ 10 $ , inclusive. - $ type $ may be "gladiator", "sentry" or "physician". - $ 1<=bonus<=100 $ . It is guaranteed that the number of residents in each item does not exceed the item's size. The names of all items and residents are pairwise different. All words and numbers in the input are separated by single spaces.

输出格式

Print on the first line the name of the weapon in the optimal equipping pattern; then print the number of residents the weapon contains; then print the residents' names. Print on the second and third lines in the same form the names of the armor and defensive orb as well as the residents they contain. Use single spaces for separation. If there are several possible solutions, print any of them.

输入输出样例

输入样例 #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 

说明

In the second sample we have no free space inside the items, therefore we cannot move the residents between them.