Maximum Subsequence / CodeForces - 888E

Input

The first line contains two integers n and m (1?≤?n?≤?35, 1?≤?m?≤?109).
The second line contains n integers a1, a2, ..., an (1?≤?ai?≤?109).

Output

Print the maximum possible value of(看右图) .

Sample Input 1

 4 4
 5 2 4 1

Sample Output

 3

Sample Input 1

 3 20
 199 41 299

Sample Output

 19

Note

题意

给n个数，求个区间，使其的和取余m最大，求最大余数

题解

折半枚举

代码

Maximum Subsequence / CodeForces - 888E

原文：https://www.cnblogs.com/Little-Turtle--QJY/p/12385949.html