零余数和

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个 $n\times m$ 的整数矩阵。你可以从每一行中选择不超过 $\lfloor m/2\rfloor$ 个元素。求所选元素之和的最大值，要求这个和能被 $k$ 整除。

可以不选择任何元素，此时和为 $0$。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$。

输出格式

输出能得到的最大且能被 $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

数据范围

对于所有数据，$1\le n,m,k\le70$，$1\le a_{i,j}\le70$。