Задачі
Максимальний модуль суми
Максимальний модуль суми
Вам дано масив a, що складається з n цілих чисел і ціле число m.
Виберіть послідовність позицій b1
, b2
, ..., bk
(1 ≤ b1
<b2 <... < bk
≤ n) таку, щоб значення було максимальне. Обрана підпослідовність може бути порожньою.
Підрахуйте максимальне можливе значення.
Вхідні дані
У першому рядку записані два цілих числа n і m(1 ≤ n ≤ 35, 1 ≤ m ≤ 109
).
У другому рядку записані n цілих чисел a[1], a[2], ..., an
(1 ≤ ai
≤ 109
).
Вихідні дані
Виведіть максимальне можливе значення.
Вхідні дані #1
4 4 5 2 4 1
Вихідні дані #1
3