Каждый предмет в игре имеет уровень. Чем выше уровень — тем более высокие базовые параметры имеет вещь. Мы будем рассматривать только следующие базовые параметры: атака (atk), защита (def) и сопротивления к различным воздействиям (res).
Каждая вещь принадлежит одному из классов. В данной задаче мы будем рассматривать только три таких класса: оружие (weapon), броня (armor), защитные сферы (orb).
Кроме того, внутри каждого предмета скрыт целый мир. С помощью путешествий в мир данного предмета можно повышать его уровень. Также в Мире Вещей можно захватывать так называемых резидентов.
Резиденты — это существа, которые живут внутри предметов. Каждый резидент дает некоторый бонус предмету, в котором он на данный момент находится. Мы будем рассматривать только резидентов типов: гладиатор (gladiator, увеличивает параметр atk предмета), часовой (sentry, увеличивает def) и целитель (physician, увеличивает res).
Каждый предмет имеет параметр вместимости. Он означает максимальное количество резидентов, которые могут жить внутри предмета. Резидентов можно перемещать между предметами. За один момент времени можно взять любого резидента в любом предмете, и переместить его в какой-либо другой предмет, если там есть место для нового жителя. При этом вынимать резидентов из предметов наружу не разрешается — каждый резидент обязательно должен быть в каком-либо предмете в любой момент времени.
У Лахарла есть некоторое количество предметов. Он хочет перераспределить резидентов между предметами таким образом, чтобы затем выбрать себе оружие, броню и защитную сферу для экипировки. При этом параметр оружия atk должен получиться максимально возможным. Из всех экипировок с максимальным параметром оружия atk параметр брони def должен быть максимальным. Из всех таких экипировок следует выбрать ту, в которой параметр защитной сферы res максимален. Значения параметров def и res у оружия, atk и res у брони и atk и def у защитной сферы Лахарлу безразличны.
Найдите оптимальную экипировку, которую Лахарл может получить.
Выходные данные
В первой строке выведите имя оружия в оптимальной экипировке, затем количество резидентов в этом оружии, после чего выведите список имен резидентов.
Во второй и третьей строке в аналогичном формате выведите имена брони и защитной сферы, а так же имена резидентов, находящихся в них.
В качестве разделителей используйте одиночные пробелы.
Если возможных решений несколько — выведите любое.
Примечание
Во втором примере свободного места в предметах нет, поэтому перемещать резидентов нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
longbow 1 mike
pagstarmor 1 bobby
iceorb 2 petr joe
|