A91479.最大模意义下子序列

给定一个包含 $n$ 个整数的数组 $a$，以及一个整数 $m$。你需要从中选择若干个下标，组成一个严格递增的下标序列

$$b_1, b_2, \dots, b_k \quad (1 \le b_1 < b_2 < \dots < b_k \le n),$$

使得下面这个值尽可能大：

$$\left(\sum_{i=1}^k a_{b_i}\right) \bmod m.$$

你也可以一个数都不选，此时视为选出的下标序列为空，和为 $0$，取模后的值为 $0$。

请你输出上述表达式可能取得的最大值。

第一行包含两个整数 $n$ 和 $m$：

• $1 \le n \le 35$，
• $1 \le m \le 10^9$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，满足：

• $1 \le a_i \le 10^9$。

输出一个整数，表示

$$\left(\sum_{i=1}^k a_{b_i}\right) \bmod m$$

在所有合法选择下标序列的方案中，能够取得的最大值。

样例解释 #1

一种最优做法是选择下标集合 $\{1, 2\}$，此时

$$a_1 + a_2 = 5 + 2 = 7,\quad 7 \bmod 4 = 3,$$

可以证明这是能够得到的最大值。

样例解释 #2

一种最优做法是只选择下标 $3$，此时

$$a_3 = 299,\quad 299 \bmod 20 = 19,$$

为可以取得的最大值。

数据范围与说明

• $1 \le n \le 35$；
• $1 \le m \le 10^9$；
• $1 \le a_i \le 10^9$；
• 你可以选择的下标序列可以为空，此时结果为 $0$。