Вам задана матрица \(a\) размера \(n \times m\), состоящая из целых чисел.
Вы можете выбрать не более \(\left\lfloor\frac{m}{2}\right\rfloor\) элементов в каждой строке. Ваша задача — выбрать эти элементы таким образом, что их сумма делится на \(k\) и эта сумма является максимальной.
Другими словами, вы можете выбрать не более половины (округленной вниз) элементов в каждой строке, вам необходимо найти максимальную сумму этих элементов, которая делится на \(k\).
Заметьте, что вы можете выбрать ноль элементов (и сумма такого множества равна \(0\)).
Выходные данные
Выведите одно целое число — максимальная сумма, делящаяся на \(k\), которую вы можете получить.
Примечание
В первом тестовом примере оптимальным ответом является взять \(2\) и \(4\) в первой строке, \(5\) и \(2\) во второй строке и \(7\) и \(4\) в третьей строке. Общая сумма равна \(2 + 4 + 5 + 2 + 7 + 4 = 24\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 3
1 2 3 4
5 2 2 2
7 1 1 4
|
24
|
|
2
|
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
|