A6277. 最大模意义下子序列

给定一个包含 $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$。