Maximum modulus of the sum#8572
You are given an array consisting of integers and an integer .
Your task is to select a sequence of positions b_1, b_2, \ldots, b_k (1 \leq b_1 < b_2 < \ldots < b_k \leq n) such that the value of the expression is maximized. Note that the chosen subsequence can be empty.
Determine the maximum possible value of this expression.
The first line contains two integers and (1 \leq n \leq 35, 1 \leq m \leq 10^9).
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9).
Print the maximum possible value.
Example 1