Миньоны много путешествовали в поисках того, кто сможет стать их новым лидеров, перед тем, как встретились с Грю. Наиолее перспективными были $$$n$$$ городов, $$$i$$$-й из которых, по их оценкам, обладает перспективностью $$$a_{i}$$$.
Разумеется, это не единственный критерий оценки городов. Миньонам также важно весело провести время. При этом посетить город $$$i$$$ можно двумя способами:
При этом в случае, когда миньоны в первый раз за всю поездку заезжают на день в какой-то город (пусть это город $$$i$$$), стоит считать $$$a_\mathtt{prev}$$$ равным $$$a_i$$$, и в таком случае они не получают удовольствия от его посещения.
Миньоны хотят посетить все города последовательно, то есть строго в порядке от $$$1$$$ до $$$n$$$, при этом, конечно же, они хотят получить от этого максимальное удовольствие. Подскажите им, какой максимальное удовольствие от такого путешествия можно получить.
При этом в города номер $$$1$$$ и номер $$$n$$$ обязательно заехать на день! Таким образом, удовольствия от посещения первого города они не получат.
В первой строке ввода даны два целых числа $$$n$$$ и $$$c$$$ — количество городов, которые миньоны хотят посетить, и параметр из условия ($$$1 \le n \le 10^6$$$; $$$-10^6 \le c \le 10^6$$$).
Во второй строке перечислены целые числа $$$a_i$$$ — значения перспективноти городов ($$$-10^6 \le a_i \le 10^6$$$).
Выведите единственное целое число — максимальное удовольствие, которое миньоны могут получить, посещая города последовательно, начиная с города под номером $$$1$$$ и заехав на день и в город $$$1$$$, и в город $$$n$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке | |
0 | – | примеры из условия | полная | ||
1 | 30 | $$$n \le 500$$$ | 0 | первая ошибка | |
2 | 20 | $$$n \le 2000$$$ | 0, 1 | первая ошибка | |
3 | 20 | $$$a_i \le a_{i+1}$$$ для всех $$$i | lt; n$$$ | первая ошибка | |
4 | 30 | без дополнительных ограничений | 0 – 3 | первая ошибка |
6 3 5 1 6 5 0 1
82
6 -1 4 4 1 1 5 9
138