CF888E.Maximum Subsequence

You are given an array $a$ consisting of $n$ integers, and additionally an integer $m$ . You have to choose some sequence of indices $b_{1},b_{2},...,b_{k}$ ( 1<=b_{1}<b_{2}<...<b_{k}<=n ) in such a way that the value of is maximized. Chosen sequence can be empty.

Print the maximum possible value of .

The first line contains two integers $n$ and $m$ ( $1<=n<=35$ , $1<=m<=10^{9}$ ).

The second line contains $n$ integers $a_{1}$ , $a_{2}$ , ..., $a_{n}$ ( $1<=a_{i}<=10^{9}$ ).

Print the maximum possible value of .

In the first example you can choose a sequence $b={1,2}$ , so the sum is equal to $7$ (and that's $3$ after taking it modulo $4$ ).

In the second example you can choose a sequence $b={3}$ .