Вам задана матрица \(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\), которую вы можете получить.
В первом тестовом примере оптимальным ответом является взять \(2\) и \(4\) в первой строке, \(5\) и \(2\) во второй строке и \(7\) и \(4\) в третьей строке. Общая сумма равна \(2 + 4 + 5 + 2 + 7 + 4 = 24\).
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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач