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

Вам задана матрица $$$a$$$ размера $$$n \times m$$$, состоящая из целых чисел.

Вы можете выбрать не более $$$\left\lfloor\frac{m}{2}\right\rfloor$$$ элементов в каждой строке. Ваша задача — выбрать эти элементы таким образом, что их сумма делится на $$$k$$$ и эта сумма является максимальной.

Другими словами, вы можете выбрать не более половины (округленной вниз) элементов в каждой строке, вам необходимо найти максимальную сумму этих элементов, которая делится на $$$k$$$.

Заметьте, что вы можете выбрать ноль элементов (и сумма такого множества равна $$$0$$$).

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

Первая строка входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m, k \le 70$$$) — количество строк в матрице, количество столбцов в матрице и значение $$$k$$$. Следующие $$$n$$$ строк содержат $$$m$$$ элементов каждая, где $$$j$$$-й элемент $$$i$$$-й строки равен $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 70$$$).

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

Выведите одно целое число — максимальная сумма, делящаяся на $$$k$$$, которую вы можете получить.

Примеры
Входные данные
3 4 3
1 2 3 4
5 2 2 2
7 1 1 4
Выходные данные
24
Входные данные
5 5 4
1 2 4 2 1
3 5 1 2 4
1 5 7 1 2
3 8 7 1 2
8 4 7 1 6
Выходные данные
56
Примечание

В первом тестовом примере оптимальным ответом является взять $$$2$$$ и $$$4$$$ в первой строке, $$$5$$$ и $$$2$$$ во второй строке и $$$7$$$ и $$$4$$$ в третьей строке. Общая сумма равна $$$2 + 4 + 5 + 2 + 7 + 4 = 24$$$.