Problem
Cat Goose preparó para Nick Fury una mesa rectangular de tamaño \(n \cdot m\) que contenía números desde 0< /span> code> a p−1. Nick Fury inmediatamente se dio cuenta de que cada número en esta tabla fue elegido al azar con igual probabilidad de 0 a p− 1 , independientemente de los demás.
Tu tarea — encuentre una submatriz rectangular de esta tabla, en la que la suma sea divisible por p. Entre todas esas submatrices, debe encontrar aquella en la que la suma de los elementos sea máxima.
Formalmente, debe encontrar
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) que la suma de
ax,y sobre todo
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) dividir en
p, y entre estos tiene la cantidad máxima.
Entrada
La primera línea contiene tres enteros n, m, p (\(1 < ;= n m, p <= 1,000,000\)) — dimensiones de la matriz y el número por el cual se debe dividir la suma de la submatriz.
Las siguientes n líneas contienen m enteros, el j-ésimo número en la i-ésima línea es igual a ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
Se garantiza que cada número en a se elija de forma independiente al azar, equiprobablemente de 0 a p−1.
Salida
Imprimir un solo entero — la suma máxima de una submatriz rectangular donde la suma es divisible por p. Si no hay ninguno, imprima 0.
Ejemplos
| # |
Entrada |
Salida |
| 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 |