题目描述

小珅来到一个 $n\times n$ 的金币仓库，从左上角走到右下角，每一步只能向下或向右移动。到达一个方格时，他可以收走其中全部金币，也可以一个也不拿。最后带走的金币总数必须是 $p$ 的倍数。请计算满足条件时最多能带走多少金币。

输入格式

第一行输入两个整数 $n,p$。

接下来 $n$ 行，每行 $n$ 个整数，表示每个方格的金币数。

输出格式

输出一个整数，表示满足整除条件的最大金币数。允许一个金币也不取。

数据范围与约定

$1\le n\le100$，$1\le p\le1000$，$0\le v_{i,j}\le1000$。

可见测试数据

输入数据 1

3 3
1 2 1
3 4 3
5 1 3

输出数据 1

12

输入数据 2

3 4
1 0 1
0 1 0
1 0 1

输出数据 2

0

输入数据 3

3 3
4 1 7
4 6 9
2 6 2

输出数据 3

21