题目描述

你面临一个简单任务. 给$n$个物品，第$i$个物品价值 $a[i]$，挑出其中一个子集，使子集中物品价值之和在 $\mod p$ 意义下最大。

输入格式

• 第一行：$2$ 个整数 $n$ 和 $p$。
• 第二行：$n$ 个非负整数 $a_i$。

输出格式

输出 $1$ 个整数，代表 $\mod p$ 下能得到的最大子集价值。

样例输入1

4 4
5 2 4 1

样例输出1

3

样例输入2

5 233
123 456 789 12 15

样例输出2

230

提示

一共有10个测试点

• 对于测试点 $1-2$: $n \leq 20$，$p \leq 100$.
• 对于测试点 $3-5$: $n \leq 100$，$p \leq 2 \times 10^5$.
• 对于测试点 $6-7$: $n \leq 25$，$p \leq 10^9$.
• 对于测试点 $8-10$: $n \leq 36$，$p \leq 10^9$.
• 对于 $100\%$ 的数据: $n \leq 100$，$a_i$，$p \leq 10^9$。

特别注意本题 $8-10$ 测试点的范围并非最大的。