e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Максимальний модуль суми

Максимальний модуль суми

Вам дано масив a, що складається з n цілих чисел і ціле число m.

Виберіть послідовність позицій b1, b2, ..., bk (1 ≤ b1 <b2 <... < bk ≤ n) таку, щоб значення z1.GIF було максимальне. Обрана підпослідовність може бути порожньою.

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

Вхідні дані

У першому рядку записані два цілих числа n і m(1 ≤ n ≤ 35, 1 ≤ m ≤ 109).

У другому рядку записані n цілих чисел a[1], a[2], ..., an(1 ≤ ai109).

Вихідні дані

Виведіть максимальне можливе значення.

Time limit 0.75 second
Memory limit 64 MiB
Input example #1
4 4
5 2 4 1
Output example #1
3