题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，以及一个整数 $m$。

选择数列 $a$ 的一个子序列，并使该子序列中所有元素之和模 $m$ 最大。

输入格式

第一行，两个整数 $n$ 和 $m$，以空格分隔（$1 \le n \le 40; 1 \le m \le 10^9$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$。

输出格式

输出一个整数，表示从数列 $a$ 中选出一些数，它们的和模 $m$ 的最大值。

样例输入1

4 4
5 2 4 1

样例输出1

3

样例输入2

3 20
199 41 299

样例输出2

19

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 20; a_i, m \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 40; 1 \le a_i, m \le 10^9$