Задача A. A money maker ≡

Условие

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

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

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

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

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

Во второй строке записано n целых чисел c₁, c₂, ... ,c_n (0 ≤ c_i ≤ 10¹⁵) - стоимость кувшина дикого огня в i-ый день.

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

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

Ограничения

2 ≤ n ≤ 100

0 ≤ x ≤ 10¹⁵

0 ≤ c_i ≤ 10¹⁵, при i = 1...n

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

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

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

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

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

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

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

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

5 10
40 37 97 3 68

84

6 2
100 1 10 40 10 40

97