Maximum Subsequence

n개의 정수로 이루어진 배열 a와 정수 m이 추가로 주어진다. 의 값이 최대가 되도록 인덱스의 수열 b1, b2, ..., bk (1 ≤ b1 < b2 < ... < bk ≤ n)을 선택해야 한다. 선택한 수열은 비어 있을 수 있다.

의 가능한 최댓값을 출력한다.

첫 번째 줄에는 두 정수 n와 m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109)이 주어진다.

두 번째 줄에는 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 109)이 주어진다.

의 가능한 최댓값을 출력한다.

첫 번째 예제에서는 수열 b = {1, 2}를 선택할 수 있으므로, 합 은 7과 같다(그리고 이를 4로 나눈 나머지는 3이다).

두 번째 예제에서는 수열 b = {3}을 선택할 수 있다.