Задача A. A money maker

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

"Наш дом всегда отдаёт долги" - сказал Мастер над монетой и призадумался. Отдавать-то долги сейчас нечем. Для того, чтобы заработать денег, Казначей хочет продать кувшин дикого огня подороже и для этого узнал, сколько будет стоить кувшин в каждый из последующих n дней. По полученным данным, в i-ый (1 ≤ i ≤ n) день кувшин дикого огня будет стоить ci золотых монет.

К сожалению, сейчас у Мастера над монетой нет ни денег, ни дикого огня, однако, он в хороших отношениях с гильдией алхимиков. Поэтому Казначей решает одолжить кувшин дикого огня "в политических целях". Алхимики готовы уступить кувшин дикого огня за x золота ровно на один день. Мастер над монетой придумал план - он хочет выбрать некоторый день j (1 ≤ j ≤ n), одолжить кувшин дикого огня и в тот же день его продать за cj золотых. На следующий j + 1-ый день на вырученные деньги Казначей хочет купить новый кувшин дикого огня по цене текущего дня за cj + 1 монет и вернуть гильдии алхимиков как дикий огонь, так и x золота за аренду.

Помогите Мастеру над монетой и выясните, сколько золотых монет он сможет заработать, проведя описанную ранее схему. Также учтите, что если на каком-либо этапе у него не хватит золота, то такой план не будет осуществлён.

Формат входных данных

В первой строке подаётся два целых числа n и x (2 ≤ n ≤ 100, 0 ≤ x ≤ 1015)- количество дней и стоимость взятия дикого огня в аренду.

Во второй строке записано n целых чисел c1, c2, ... ,cn (0 ≤ ci ≤ 1015) - стоимость кувшина дикого огня в i-ый день.

Формат выходных данных

Выведите одно единственное число - максимально возможный заработок при осуществлении плана. Если план не может быть осуществлен, выведите 0.

Ограничения

2 ≤ n ≤ 100

0 ≤ x ≤ 1015

0 ≤ ci ≤ 1015, при i = 1...n

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
xci
1101 ≤ x ≤ 1001 ≤ ci ≤ 100
2351 ≤ x ≤ 100001 ≤ ci ≤ 10000
3551 ≤ x ≤ 10151 ≤ ci ≤ 1015

Пояснение к примерам

В первом примере оптимально арендовать и продать кувшин, когда он стоит 97 монет, и выкупить обратно на следующий день по цене в 3 монеты, за вычетом стоимости займа прибыль составила 84 зотолые монеты.

Аналогично первому примеру, арендуем кувшин в первый день, прибыль составляет 97 золотых монет.

Примеры тестов

Стандартный вход Стандартный выход
1
5 10
40 37 97 3 68
84
2
6 2
100 1 10 40 10 40
97

0.088s 0.009s 13