题目描述

给定一个由整数构成的 $n \times m$ 的矩阵 $a$。

你可以在每一行中选择不超过 $\left\lfloor\frac{m}{2}\right\rfloor$ 个元素。你的任务是选择这些元素，使得它们的和能被 $k$ 整除，并且这个和最大。

换句话说，你可以在每一行中选择不超过一半（向下取整）的元素，你需要找到这些元素的最大和，并且这个和能被 $k$ 整除。

注意，你可以选择 $0$ 个元素（此时和为 $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$ 整除的和。

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$。