Соревнования
Queue Data Structure
Отели на хорватском побережье
Вдоль прекрасного Адриатического побережья расположено n отелей. Каждый отель имеет свою стоимость в евро.
Петр выиграл m евро в лотерею. Теперь он хочет купить последовательность следующих друг за другом отелей так, чтобы сумма стоимостей этих последовательных отелей была как можно больше, но не превышала m.
Вы должны рассчитать эту максимально возможную общую стоимость.
Входные данные
В первой строке заданы два целых числа n и m~(1 \le n \le 3 \cdot 10^5, 1 \le m < 2^{31}). В следующей строке заданы n натуральных чисел меньших 10^6, представляющих стоимости отелей в том порядке, в котором они расположены вдоль побережья.
Выходные данные
Выведите искомую максимальную стоимость (оно будет больше 0 во всех тестах).
Пример
Входные данные #1
5 12 2 1 3 4 5
Выходные данные #1
12