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

Вам дан массив a, состоящий из n целых чисел, и целое число m.

Необходимо выбрать последовательность индексов b[1], b[2], ..., b[k] (1 ≤ b[1] < b[2] < ... < b[k] ≤ n) так, чтобы значение было максимальным. Выбранная подпоследовательность может быть пустой.

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

Входные данные

Первая строка содержит два целых числа n и m (1 ≤ n ≤ 35, 1 ≤ m ≤ 10^9).

Вторая строка содержит n целых чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9).

Выходные данные

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

Примеры