CF888E Maximum Subsequence

给定一个包含 $n$ 个整数的数组 $a$，以及一个整数 $m$。你需要选择若干个索引序列 $b_1, b_2, \dots, b_k$（$1 \le b_1 < b_2 < \dots < b_k \le n$），使得下式的值最大化： $$ \left(\sum\limits_{i=1}^k a_{b_i}\right) \bmod m $$ 你可以选择的序列也可以为空。 请输出上述表达式可能取得的最大值。

第一行包含两个整数 $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}$）。

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

在第一个样例中，你可以选择序列 $b = \{1, 2\}$，这样 $\sum a_{b_i} = 7$（模 $4$ 之后为 $3$，其值最大）。 在第二个样例中，你可以选择序列 $b = \{3\}$。 由 ChatGPT 5 翻译