Given an array
A consisting of
n positive integers and a number
m. Select the sequence of positions
B 1,
B2, ...,
Bk (1 <= B
1 < B
2 < ... < B
k <= n) such that ;
\((\sum_{i=1}^{k} A_{B_i}) mod \; m\) was the maximum (that is, so that the remainder of dividing the sum of the elements of the subsequence by the number
m is the maximum possible). The selected sequence can be empty.
Calculate the maximum possible value of
\((\sum_{i=1}^{k} A_{B_i}) mod \; m\).
Input
The first line contains two integers
n and
m (1 <= n <= 35, 1 <= m <= 10
9). The second line contains n integers A1, A2< /code>, ..., An (1 <= Ai <= 109 )
Imprint
Output one number - the maximum value \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)
Examples
| # |
Input |
Output |
| 1 |
4 4
5 2 4 1
| 3 |
| 2 |
3 20
199 41 299
| 19 |
Explanations
In the first example, you can choose B = {1, 2}. (A1 + A2) mod m = (5 + 2) % 4 = 3.
In the second example, you can select B = {3}.