Дан массив
A, состоящий из
n целых положительных чисел, и число
m. Выберите последовательность позиций
B1,
B2, ...,
Bk (1 <= B
1 < B
2 < ... < 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
9). Во второй строке дано
n целых чисел
A1,
A2, ...,
An (1 <= A
i <= 10
9)
Выходные данные
Выведите одно число - максимальное значение
\((\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}.