Орлине Гніздо#1110
"Орлине Гніздо" — це пригодницька екшн-гра. Гравець має на меті виконувати завдання й долати дедалі складніші місії, розвиваючи свої навички та досягаючи вищих результатів. Однак досягти успіху в цій грі непросто.
Гра має нелінійний сюжет, що дозволяє гравцеві обирати серед кількох альтернативних місій. Є одне правило: гравець може вибирати лише ті місії, які складніші за всі місії, які він уже виконав. Після проходження місії вона більше не доступна для гравця. Єдині винятки — це перша та остання місії: їх ніколи не прибирають і вони не з'являються у списку доступних. Як ви могли здогадатися, це найлегша й найскладніша місії відповідно. Можна завершити гру, не виконавши багато місій. Щоб заохотити тих, хто проходить максимум місій, у грі передбачені особливі досягнення та визнання.
Для найвідданіших гравців передбачено ще привабливіші нагороди. Нехай — максимальна кількість місій, які можна виконати за один захід. Якщо гравець зуміє пройти гру кілька разів (кожного разу починаючи з першої місії і завершуючи останньою), щоразу виконуючи рівно місій і досягаючи максимуму в заданих умовах, усі місії буде повністю відкрито, і гравець отримає особливе визнання.
Ваше завдання просте: допоможіть відданому гравцеві визначити максимальну кількість місій, які можна пройти за наведених обмежень. Порядок проходження місій у кожній грі важливий і має відповідати сюжетній лінії.
Перший рядок містить одне ціле число (2 < n < 100). Далі у кожному з наступних рядків подано назву місії та її рівень складності. Назва місії — це рядок до символів, а рівень складності — додатне ціле число. Назви місій чутливі до регістру й можуть містити лише латинські літери, цифри та символ підкреслення. Рівень складності не перевищує 10^8. У жодному тесті назви місій не повторюються.
Виведіть максимально можливу кількість місій, які можна виконати за наведених обмежень. Це число не враховує першу й останню місії.
Приклад 1
Приклад 2