Задача . Максимальная по модулю подпоследовательность

Дан массив A, состоящий из n целых положительных чисел, и число m. Выберите последовательность позиций B1, B2, ..., Bk (1 <= B₁ < B₂ < ... < B_k <= n) такую, чтобы значение  \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) было максимально (то есть, чтобы остаток от деления суммы элементов подпоследовательности на число m был максимально возможным). Выбранная последовательность может быть пустой.
Посчитайте максимальное возможно значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Входные данные
В первой строке даны два целых числа n и m (1 <= n <= 35, 1 <= m <= 10⁹). Во второй строке дано n целых чисел A1, A2, ..., An (1 <= A_i <= 10⁹)

Выходные данные
Выведите одно число - максимальное значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 

Примеры

№	Входные данные	Выходные данные
1	4 4 5 2 4 1	3
2	3 20 199 41 299	19

 

Пояснения

В первом примере можно выбрать B = {1, 2}. (A1 + A2) mod m = (5 + 2) % 4 = 3.
Во втором примере можно выбрать B = {3}.