题目描述

给你一个 $n \time m$ 的整数矩阵 $a$，它一共有 $n$ 行，每一行包含 $m$ 个整数，我们用 $a_{i,j}$ 表示第 $i$ 行的第 $j$ 个整数。

每一行你最多可以选择 $\lfloor \frac{m}{2} \rfloor$ 个数（这里 $\lfloor x \rfloor$ 表示 $x$ 向下取整的结果）。你的任务是在满足这个约束条件的情况下从整数矩阵中选出一些数，使得它们的和能被 $k$ 整除且它们的和最大。输出这个最大的和。

（注：你可以一个元素都不选，此时对应的和为 $0$）

输入格式

输入的第一行包含三个整数 $n,m,k(1 \le n,m,k \le 70)$，以空格分隔。

接下来 $n$ 行每行包含 $m$ 个整数，每一行的相邻元素间以一个空格分隔，其中第 $i+1$ 行的第 $j$ 个整数表示 $a_{i,j}(1 \le a_{i,j} \le 70)$。

输出格式

输出一个整数，即 —— 在满足每一行选择的元素个数不超过 $\lfloor \frac{m}{2} \rfloor$ 的前提下所选的数的能被 $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

样例 1 解释

对于样例1，可以在第一行选择 $2,4$，第二行选择 $5,2$，第三行选择 $7,4$，于是它们的总和为 $2+4+5+2+7+4=24$。

数据范围

• 对于 $20\%$ 的数据，$n,m \le 5$；
• 对于 $40\%$ 的数据，$n,m,k \le 20$；
• 对于 $100\%$ 的数据 $1 \le n,m,k,a_{i,j} \le 70$。