Как известно, идеальный отряд состоит из война, мага, клирика и разбойника. Однако иногда приходится обходиться меньшим: войн, маг и клирик могут образовать отряд из трёх человек, который будет не идеальным. Можно составить отряд и из одного война, если больше некуда деваться.
В вашей гильдии состоит n человек. Каждый человек обладает набором квалификаций: он может быть воином, магом, клириком и/или разбойником. А именно, человек обладает любым непустым подмножеством квалификаций, то есть, он может иметь произвольный набор из одной, двух, трёх или четырёх квалификаций.
Чтобы собрать отряд, нужно взять до четырёх человек и дать каждому роль, соответствующую одной из его квалификаций. На каждую роль можно назначить не более одного человека, и одному человеку нельзя дать две роли сразу, даже если он обладает несколькими квалификациями. Таким образом, в отряде будет не более одного человека в роли война, не более одного человека в роли мага и т.д., и всего будет занято ролей столько, сколько человек в отряде.
Вам нужно собрать один отряд наибольшего размера, и если этот отряд не идеален — разместить объявление о приёме новых людей в гильдию. Чтобы составить объявление, требуется для каждой из четырёх квалификаций выяснить, увеличится ли максимальный возможный размер отряда, если нанять человека только с этой квалификацией.
Исходные данные
В первой строке дано единственное целое число n — количество людей в гильдии (1 ≤ n ≤ 15).
Каждая из следующих n строк содержит от 1 до 4 заглавных букв W
(Воин), M
(Маг), C
(Клирик), R
(Разбойник), не разделённых пробелом, обозначающих набор квалификаций очередного человека. Буквы будут идти именно в таком порядке, то есть каждая из этих строк получается из строки WMCR
удалением не более трёх букв.
Результат
В первой строке выведите единственное число — наибольший размер отряда, который можно собрать.
Если наибольший размер отряда меньше 4, выведите ещё одну строку, начинающуюся с «Looking for
», где далее через пробел перечислены квалификации в объявлении. Каждая квалификация — это одно из четырёх слов: «warrior
» (Воин), «mage
» (Маг), «cleric
» (Клирик) или «rogue
» (Разбойник), именно в таком порядке. Указывать нужно такие квалификации, что при найме одного человека с только одной из этих квалификаций наибольший размер отряда увеличится.
Примеры
исходные данные | результат |
---|
1
W | 1
Looking for mage cleric rogue |
2
M
CR | 2
Looking for warrior cleric rogue |
4
WMCR
WMCR
WMCR
WMCR | 4 |
1
WMCR | 1
Looking for warrior mage cleric rogue |
Автор задачи: Валентин Зуев
Источник задачи: Уральская командная олимпиада по программированию 2020