F. Zero Remainder Sum

You are given a matrix a of size n×m consisting of integers.

You can choose no more than $\left\lfloor\frac{m}{2}\right\rfloor$ elements in each row. Your task is to choose these elements in such a way that their sum is divisible by k and this sum is the maximum.

In other words, you can choose no more than a half (rounded down) of elements in each row, you have to find the maximum sum of these elements divisible by k.

Note that you can choose zero elements (and the sum of such set is 00).

Input

The first line of the input contains three integers n, mm and k (1≤n,m,k≤70) — the number of rows in the matrix, the number of columns in the matrix and the value of k. The next n lines contain mm elements each, where the j-th element of the i-th row is $a_{i,j} (1≤a_{i,j}≤70)$.

Output

Print one integer — the maximum sum divisible by k you can obtain.

Examples

input

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

output

1
24

题意：一个矩阵每一行至多选择$\left\lfloor\frac{m}{2}\right\rfloor$ 个数，且最后总和 sum 能被 k 整除。

设 $d[i][j][c][r]$ 表示取到第（i，j）个元素，第 i 行取了 c 个时，余数为 r 时的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int MAX=70+10;
int n,m,k,a[MAX][MAX],d[MAX][MAX][MAX][MAX];
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);sf(k);
	fi(i,0,n) fi(j,0,m) sf(a[i][j]);
	mem(d,-0x3f);
	d[0][0][0][0]=0;
	fi(i,0,n) fi(j,0,m) fi(c,0,m/2+1) fi(r,0,k){
		if(d[i][j][c][r]==-INF) continue;
		if(j==m-1){
			d[i+1][0][0][r] = max(d[i+1][0][0][r],d[i][j][c][r]);
		}else {
			d[i][j+1][c][r] = max(d[i][j+1][c][r],d[i][j][c][r]);
		}
		if(c<(m/2)){
			int t = (r+a[i][j])%k;
			if(j==m-1){
				d[i+1][0][0][t] = max(d[i+1][0][0][t] ,d[i][j][c][r]+a[i][j]);
			}else {
				d[i][j+1][c+1][t] = max(d[i][j+1][c+1][t],d[i][j][c][r]+a[i][j]);
			}
		}
	}
	pfn(d[n][0][0][0]);
	return 0;
}