题目描述

给定n个整数，从中选出若干个数字(每个数字最多选一次)，使得它们的和取余m最大，求最大的余数。

输入

第一行输入两个整数n($1 \leq n \leq 35$)和m($1 \leq m \leq 10^9$)

第二行输入n个整数，这些整数属于区间[1,$10^9$]

输出

输出一个整数

样例

4 4
5 2 4 1

3

3 20
199 41 299

19

2 10
2 2

4