Гніздо орла
"Гніздо орла" являє собою пригодницьку гру. Основний зміст гри полягає у знищенні поганих хороших хлопців, створенні суспільного порядку, зборі грошей з незаконної діяльностіи, поступово перетворюючись в успішного гангстера. Але бути гангстером не так просто у цій грі.
Гра має нелінійну сюжетну лінію, яка дозволяє гравцю обирати одну з декількох альтернативних місій. Проте тут криється одна западня. Гравець кожен раз може обирати місії, складність яких більша ніж довільна з попередніх завершених. І коли місію завершено, вона бвльше не доступна гравцю. Єдиний виняток складають перша і остання місії, які ніколи не видаляються і навіть не подані у списку можливих місій. Як Ви вже здогадались, це відповідно сама легка і сама важка місії. Очевидно, що гру можна завершити, не зіграши багато місій. Саме тому розробники гри запропонували деякі бонуси тим, хто зможе зіграти найбільшу кількість місій. І повірте, бонуси варті того. Ви отримаєте більше здоров'єя, зброї і інших речей для перемоги!
Для зацікавлених гравців існуєть ще більш приголомшливі новини. Нехай k - максимальна кількість місій, яка може бути завершена, коли гравець завершує гру перший раз. Якщо хтось зможе пройти гру декілька разів (починаючи з першої місії і завершуючи останньою) таким чином, що в точності k місій буде завершено кожен раз за гру, і при цьому буде зіграно найбільшу кількість ігор при заданих обмеженнях, то гравець отримає нескінченну кількість зброї і непереможність. І це ще не все; всі місії будуть відкриті для гравця. А це значить, що буде і нескінченна зброя, нескінченне здоров'я, а також нескінченне число хороших хлопців у Вашій владі.
Ваша задача проста і очевидна. Необхідно зацікавленому гравцю допомогти вибрати максимальну кількість місій, яку можна завершити при заданих обмеженнях. Порядок місій у кожній грі важливий, він повинен будуватись згідно сюжетної лінії.
Вхідні дані
Перший рядок містить значення n (2 < n < 100). Кожен з наступних n рядків містить назву місії і рівень її складності. Назва місії містить до 20 символів, а рівень складності характеризує додатнє ціле число. Символи у назві місії чуттєві до регістру, і можуть містити лише букви, числа і символ підкреслення. Рівень складності не більший 10^8. Назви місій у кожному тесті не дублюються.
Вихідні дані
Вивести максимальну кількість місій, яку може бути завершено при заданих обмеженнях. Це число повинно не включати у себе первшу і останню місію.