eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Гнездо орла

Гнездо орла

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
prb1110

"Гнездо орла" представляет собой приключенческую игру. Основной смысл игры состоит в уничтожении хороших парней, создании общественного порядка, сборе денег с незаконной деятельности, постепенно превращаясь в успешного гангстера. Но быть гангстером не так просто в этой игре.

Игра имеет нелинейную сюжетную линию, которая позволяет игроку выбирать одну из нескольких альтернативных миссий. Однако здесь есть одна ловушка. Игрок каждый раз может выбирать миссии, сложность которых больше чем любая из предыдущих законченных. И когда миссия закончена, она больше не доступна игроку. Единственное исключение составляют первая и последняя миссии, которые никогда не удаляются и даже не представлены в списке возможных миссий. Как Вы уже догадались, это соответственно самая легкая и самая трудная миссии. Очевидно, что игру можно закончить, не сыграв много миссий. Именно поэтому разработчики игры предложили некоторые бонусы тем, кто сможет сыграть наибольшее количество миссий. И поверьте, бонусы стоят того. Вы получите больше здоровья, оружия и других вещей для победы!

Для заинтересованных игроков существуют еще более потрясающие новости. Пусть k - максимальное количество миссий, которое может быть закончено, когда игрок завершает игру первый раз. Если кто-то сможет пройти игру несколько раз (начиная с первой миссии и заканчивая последней) таким образом, что в точности k миссий будет завершено каждый раз за игру, и при этом будет сыграно наибольшее количество игр при заданных ограничениях, то игрок получит бесконечное количество оружия и непобедимость. И это еще не все; все миссии будут открыты для игрока. А это значит, что будут и бесконечное оружие, бесконечное здоровье, а также бесконечное число хороших парней в Вашей власти.

Ваша задача проста и очевидна. Необходимо заинтересованному игроку помочь выбрать максимальное количество миссий, которое можно закончить при заданных ограничениях. Порядок миссий в каждой игре важен, он должен строиться согласно сюжетной линии.

Входные данные

Первая строка содержит значение n (2 < n < 100). Каждая из следующих n строк содержит название миссии и уровень ее сложности. Название миссии содержит до 20 символов, а уровень сложности характеризует положительное целое число. Символы в названии миссии чувствительны к регистру, и могут содержать только буквы, числа и символ подчеркивания. Уровень сложности не более 10^8. Название миссии в каждом тесте не дублируется.

Выходные данные

Вывести максимальное количество миссий, которое может быть завершено при заданных ограничениях. Это число должно не включать в себя первую и последнюю миссию.

Пример

Входные данные #1
3
Rob_The_Cop 6
A_Petty_Thief 5
Meet_The_Boss 3
Выходные данные #1
3
Входные данные #2
3
Meet_The_Boss 3
Rob_The_Cop 6
A_Petty_Thief 5
Выходные данные #2
2
Источник Летняя Школа 2010, Севастополь, день М.Медведева