Cat Goose prepared for Nick Fury a rectangular table a of size \(n \cdot m\) containing numbers from 0 code> to p−1. Nick Fury immediately realized that each number in this table was chosen randomly with equal probability from 0 to p−1 , regardless of the others.
Your task — find a rectangular submatrix of this table, in which the sum is divisible by p. Among all such submatrices, you need to find the one in which the sum of the elements is maximum.
Formally, you need to find
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) that the sum of
ax,y over all
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) split on
p, and among these has the maximum amount.
Input
The first line contains three integers n, m, p (\(1 <= n m, p <= 1,000,000\)) — dimensions of the matrix and the number by which the sum of the submatrix should be divided.
The following n lines contain m integers, the j-th number in the i-th line equals ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
It is guaranteed that each number in a is chosen independently at random, equiprobably from 0 to p−1.
Output
Print a single integer — the maximum sum of a rectangular submatrix where the sum is divisible by p. If there are none, print 0.
Examples
| # |
Input |
Output |
| 1 |
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
|
65 |