E. Максимальная подпоследовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив a, состоящий из n целых чисел и целое число m. Выберите последовательность позиций b1, b2, ..., bk (1 ≤ b1 < b2 < ... < bk ≤ n) такую, чтобы значение было максимально. Выбранная подследовательность может быть пустой.

Подсчитайте максимальное возможное значение .

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109).

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109).

Выходные данные

Выведите максимальное возможное значение .

Примеры
Входные данные
4 4
5 2 4 1
Выходные данные
3
Входные данные
3 20
199 41 299
Выходные данные
19
Примечание

В первом примере можно выбрать последовательность b = {1, 2}, чтобы сумма была равна 7 (равна 3 по модулю 4).

Во втором примере можете выбрать последовательность b = {3}.