Задачі
Готелі на хорватському узбережжі
Готелі на хорватському узбережжі
Уздовж прекрасного Адріатичного узбережжя розташовано 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