MP3-плеєр
Новий MP3-плеєр Георга має багато цікавих функцій, одна з яких — блокування клавіш. Усі клавіші блокуються після більше ніж T секунд бездіяльності. Після активації блокування жодна клавіша не виконує свою початкову функцію, але якщо натиснути будь-яку клавішу, блокування знімається.
Наприклад, припустимо, що T = 5 і плеєр наразі заблокований. Георг натискає клавішу A, чекає 3 секунди, натискає клавішу B, чекає 5 секунд, натискає клавішу C, чекає 6 секунд і натискає D. У цьому випадку лише клавіші B та C виконують свої звичайні функції. Зверніть увагу, що клавіші були заблоковані між натисканням C та D.
Рівень звуку MP3-плеєра контролюється клавішами + та -, які відповідно збільшують та зменшують гучність на 1 одиницю. Рівень звуку — це ціле число між 0 та V_max. Натискання клавіші + при гучності V_max або натискання клавіші - при гучності 0 залишає гучність незмінною.
Георг не знає значення T. Він хотів знайти його за допомогою експерименту. Починаючи з заблокованої клавіатури, він натиснув послідовність з N клавіш + та -. Наприкінці експерименту Георг прочитав кінцеву гучність з дисплея плеєра. На жаль, він забув зазначити гучність перед першим натисканням клавіші. Для цілей цього завдання невідома початкова гучність буде позначена як V_1, а відома кінцева гучність буде позначена як V_2.
Вам дано значення V_2 та список натискань клавіш у порядку, в якому Георг їх виконав. Для кожної клавіші вам дано тип клавіші (+ або -) та кількість секунд від початку експерименту до моменту, коли клавішу було натиснуто. Завдання полягає в тому, щоб знайти найбільше можливе ціле значення T, яке узгоджується з результатом експерименту.
Вхідні дані
Перша строка вхідних даних містить три цілі числа, розділені пробілами: N, V_max та V_2 (0 ≤ V_2 ≤ V_max). Кожна з наступних N строк містить опис однієї клавіші в послідовності: символ + або -, пробіл і ціле число C_i (0 ≤ C_i ≤ 2·10^9), кількість секунд від початку експерименту. Ви можете припустити, що натискання клавіш відсортовані за порядком і що всі часи є унікальними (тобто C_i < C_{i+1} для всіх 1 ≤ i < N).
Обмеження
Ви можете припустити, що 2 ≤ N ≤ 100000 і 2 ≤ V_max ≤ 5000.
У тестових випадках, які варті 40 балів, N ≤ 4000.
У тестових випадках, які варті 70 балів, N·V_max ≤ 400000.
Вихідні дані
Якщо T може бути довільно великим, виведіть один рядок, що містить слово "infinity" (лапки для ясності).
Інакше виведіть один рядок, що містить два цілі числа T та V_1, розділені одним пробілом.
Значення повинні бути такими, що проведення експерименту з часом блокування T, починаючи з гучності V_1, дає кінцеву гучність V_2. Якщо існує кілька можливих відповідей, виведіть ту, що має найбільше T; якщо все ще існує кілька можливих відповідей, виведіть ту, що має найбільше V_1.
(Зверніть увагу, що завжди існує хоча б одне рішення: для T = 0 жодна з клавіш не виконує свою дію, тому достатньо взяти V_1 = V_2.)