MP3-плеєр#5344

MP3-плеєр

1 секунда

256 мегабайтів

Дуже складна

Новий MP3-плеєр Георга має багато цікавих функцій, одна з яких — блокування клавіш. Усі клавіші блокуються після більше ніж $T$ секунд бездіяльності. Після активації блокування жодна клавіша не виконує свою початкову функцію, але якщо натиснути будь-яку клавішу, блокування знімається.

Наприклад, припустимо, що $T = 5$ T = 5 і плеєр наразі заблокований. Георг натискає клавішу $A$ , чекає $3$ секунди, натискає клавішу $B$ , чекає $5$ секунд, натискає клавішу $C$ , чекає $6$ секунд і натискає $D$ . У цьому випадку лише клавіші $B$ та $C$ виконують свої звичайні функції. Зверніть увагу, що клавіші були заблоковані між натисканням $C$ та $D$ .

Рівень звуку MP3-плеєра контролюється клавішами $+$ та $-$ , які відповідно збільшують та зменшують гучність на $1$ одиницю. Рівень звуку — це ціле число між $0$ та $V_{ma x}$ V_{max}. Натискання клавіші $+$ при гучності $V_{ma x}$ V_{max} або натискання клавіші $-$ при гучності $0$ залишає гучність незмінною.

Георг не знає значення $T$ . Він хотів знайти його за допомогою експерименту. Починаючи з заблокованої клавіатури, він натиснув послідовність з $N$ клавіш $+$ та $-$ . Наприкінці експерименту Георг прочитав кінцеву гучність з дисплея плеєра. На жаль, він забув зазначити гучність перед першим натисканням клавіші. Для цілей цього завдання невідома початкова гучність буде позначена як $V_{1}$ V_1, а відома кінцева гучність буде позначена як $V_{2}$ V_2.

Вам дано значення $V_{2}$ V_2 та список натискань клавіш у порядку, в якому Георг їх виконав. Для кожної клавіші вам дано тип клавіші ( $+$ або $-$ ) та кількість секунд від початку експерименту до моменту, коли клавішу було натиснуто. Завдання полягає в тому, щоб знайти найбільше можливе ціле значення $T$ , яке узгоджується з результатом експерименту.

Вхідні дані

Перша строка вхідних даних містить три цілі числа, розділені пробілами: $N$ , $V_{ma x}$ V_{max} та $V_{2}$ V_2 ( $0 \leq V_{2} \leq V_{ma x}$ 0 \leq V_2 \leq V_{max}). Кожна з наступних $N$ строк містить опис однієї клавіші в послідовності: символ $+$ або $-$ , пробіл і ціле число $C_{i}$ C_i ( $0 \leq C_{i} \leq 2 \cdot 1 0^{9}$ 0 \leq C_i \leq 2 \cdot 10^9), кількість секунд від початку експерименту. Ви можете припустити, що натискання клавіш відсортовані за порядком і що всі часи є унікальними (тобто $C_{i} < C_{i + 1}$ C_i < C_{i+1} для всіх $1 \leq i < N$ 1 \leq i < N).

Обмеження

Ви можете припустити, що $2 \leq N \leq 100000$ 2 \leq N \leq 100000 і $2 \leq V_{ma x} \leq 5000$ 2 \leq V_{max} \leq 5000.

У тестових випадках, які варті $40$ балів, $N \leq 4000$ N \leq 4000.

У тестових випадках, які варті $70$ балів, $N \cdot V_{ma x} \leq 400000$ N \cdot V_{max} \leq 400000.

Вихідні дані

Якщо $T$ може бути довільно великим, виведіть один рядок, що містить слово "infinity" (лапки для ясності).

Інакше виведіть один рядок, що містить два цілі числа $T$ та $V_{1}$ V_1, розділені одним пробілом.

Значення повинні бути такими, що проведення експерименту з часом блокування $T$ , починаючи з гучності $V_{1}$ V_1, дає кінцеву гучність $V_{2}$ V_2. Якщо існує кілька можливих відповідей, виведіть ту, що має найбільше $T$ ; якщо все ще існує кілька можливих відповідей, виведіть ту, що має найбільше $V_{1}$ V_1.

(Зверніть увагу, що завжди існує хоча б одне рішення: для $T = 0$ T = 0 жодна з клавіш не виконує свою дію, тому достатньо взяти $V_{1} = V_{2}$ V_1 = V_2.)

Приклади

Приклад 1