该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目：子集和的最大余数求解

题目描述

给定 $n$ 个整数 $a_1, a_2, \cdots, a_n$ 以及一个整数 $m$ ，需要从这 $n$ 个给定数字里挑选任意多个数字，使它们的和除以 $m$ 所得的余数尽可能大，最后输出这个最大余数。

输入格式

• 第一行：两个整数 $n$ 和 $m$ ，分别表示给定数字的个数以及除数。
• 第二行：$n$ 个整数 $a_1, a_2, \cdots, a_n$ ，代表给定的数字。

输出格式

输出一个整数，即满足条件的最大余数。

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq10$ 。
• 对于 $60\%$ 的数据，$1\leq n\leq20$ 。
• 对于 $100\%$ 的数据，$1\leq n\leq40$ ，$1\leq a_i\leq10^9$ ，$1\leq m\leq10^9$ 。

示例

• 输入

5 233
1 10 100 1000 10000

• 输出

225

• 说明：选择部分数字相加得到 $10011$ ，$10011\bmod{233} = 225$ ，这就是能得到的最大余数。