Автор: | Денис Лысенко | Ограничение времени: | 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
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
x | ci | ||
1 | 10 | 1 ≤ x ≤ 100 | 1 ≤ ci ≤ 100 |
2 | 35 | 1 ≤ x ≤ 10000 | 1 ≤ ci ≤ 10000 |
3 | 55 | 1 ≤ x ≤ 1015 | 1 ≤ ci ≤ 1015 |
В первом примере оптимально арендовать и продать кувшин, когда он стоит 97 монет, и выкупить обратно на следующий день по цене в 3 монеты, за вычетом стоимости займа прибыль составила 84 зотолые монеты.
Аналогично первому примеру, арендуем кувшин в первый день, прибыль составляет 97 золотых монет.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|