Problem 1052 --C.红包

1052: C.红包

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 449  Solved: 67
[Submit][Status][Web Board][Creator:]

Description

一年一度的春节到了,Alice又可以愉快的接受她的土豪亲戚的红包了,真是激动不已!

Alice有n(1 ≤ n ≤ 18)个亲戚,每个亲戚都给Alice准备了ai(1 ≤ ai ≤ 109)元红包,但是严肃的妈咪为了控制Alice的钱,规定Alice只能取 求和(i=1 到 k) abimod m 元,其中b1, b2, ..., bk 满足1 ≤ b1 < b2 < ... < bknm满足1 ≤ m ≤ 109

Alice当然想尽可能的获得更多的钱,她向Bob求助请求Bob给出一个最好的方案,Bob把编写程序的重要任务再一次甩给了你。

Input

第一行输入两个整数n 和m (1 ≤ n ≤ 181 ≤ m ≤ 109)。

接下来一行包括n个整数 a1a2, ..., an (1 ≤ ai ≤ 109)。

Output

输出一个整数即最大值。

Sample Input

4 4
5 2 4 1
3 20
199 41 299

Sample Output

3
19

HINT


1、请仔细分析样例



2、 求和(i=1 到 k) abimod m  这里求和就是Σ符号

Source

[Submit][Status]