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 .

给你一个由 $ n $ 个整数组成的数组 $ a $，以及一个额外的整数 $ m $。你需要选择一个下标序列 $ b_1,,b_2,,\dots,,b_k $（满足 $ 1 \leq b_1 < b_2 < \dots < b_k \leq n $），使得表达式

的值最大化。所选序列可以为空。

请输出该表达式可能取得的最大值：

The first line contains two integers n and m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109).

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 35$，$1 \le m \le 10^9$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 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}.

在第一个例子中，你可以选择序列 $ b = {1, 2} $，此时和 等于 7（对 4 取模后为 3）。

在第二个例子中，你可以选择序列 $ b = {3} $。