← 返回题目列表

Codeforces · 888/E

E. 最大子序列

中文机器翻译题面 查看原题

给定一个由 n 个整数组成的数组 a,以及一个整数 m。您必须选择一些索引序列 b1, b2, ..., bk (1 ≤ b1 < b2 < ... < bk ≤ n),以使 $$\sum_{i=1}^{k} a_{b_i} \bmod m$$ 的值最大化。所选序列可以为空。

打印 $$\sum_{i=1}^{k} a_{b_i} \bmod m$$ 的最大可能值。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109)。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。

输出

打印 $$\sum_{i=1}^{k} a_{b_i} \bmod m$$ 的最大可能值。

示例

输入 #1

4 4
5 2 4 1

输出 #1

3

输入 #2

3 20
199 41 299

输出 #2

19

注意

在第一个示例中,您可以选择序列 b = {1, 2},因此总和 $$\sum_{i=1}^{k}a_{bi}$$ 等于 7(模 4 后为 3)。

在第二个示例中,您可以选择序列 b = {3}。