Автор: | Денис Лысенко | Ограничение времени: | 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 |
|
|