题目描述

给一个长度为 $n$ 的数列 $a_i$，和一个整数 $m$，在数列任选若干个数，使得他们的和对 $m$ 取模后最大。

输入格式

第一行两个整数 $n,m$，$1\le n\le 35$，$1\le 10^9$。

第二行 $n$ 个整数 $a_i$，$1\le a_i\le 10^9$。

输出格式

输出对 $m$ 取模后的最大和。

4 4
5 2 4 1

3

3 20
199 41 299

19