题目描述

给定 $n$ 个数字 $a_1,a_2,\dots,a_n$，在给定一个整数 $m$，请从给定的数字中挑选任意多个数字，使得它们的和模 $m$ 的余数尽量大，输出这个最大的余数。

输入格式

• 第一行：两个整数 $n$ 与 $m$
• 第二行：$n$ 个整数 $a_1,a_2,\dots,a_n$

输出格式

• 单个整数表示答案

5 233
1 10 100 1000 10000

225

样例解释 1

10011 mod 233 = 225

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 10$；
• 对于 $60\%$ 的数据，$1\leq n\leq 20$；
• 对于 $100\%$ 的数据，$1\leq n\leq 40$
• $1\leq a_i\leq 10^9$；
• $1\leq m\leq 10^9$；