Description

给定n个数的序列A1，A2...An，再给定一个数m，你可以从序列A中选取若干个数加起来得到sum，然后sum%m，请问取模后得到的最大值可以是多少?

Format

Input

第一行输入n和m，（1<=n<=30，5<=m<=1e9）

第二行输入n个数，代表序列A，（1<=Ai<=1e9）

Output

输出最大值

Samples

3 5
3 6 2

4

Limitation

1s, 1024KiB for each test case.