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.)