eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Готелі на хорватському узбережжі

Готелі на хорватському узбережжі

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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