← 返回题目列表

Codeforces · 1433/F

F. 零余数和

中文机器翻译题面 查看原题

给定一个矩阵 $$$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$$$ 元素,其中第 $$$i$$$ 行的第 $$$j$$$ 元素是 $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 70$$$)。

输出

打印一个整数——可以被 $$$k$$$ 整除的最大和。

示例

输入 #1

3 4 3
1 2 3 4
5 2 2 2
7 1 1 4

输出 #1

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

输出 #2

56

注意

在第一个示例中,最佳答案是第一行中的 $$$2$$$ 和 $$$4$$$,第二行中的 $$$5$$$ 和 $$$2$$$ 以及第三行中的 $$$7$$$ 和 $$$4$$$。总和为 $$$2 + 4 + 5 + 2 + 7 + 4 = 24$$$。