Problem
Cat Goose preparou para Nick Fury uma mesa retangular a de tamanho \(n \cdot m\) contendo números de 0< /span> código> para p−1. Nick Fury percebeu imediatamente que cada número nesta tabela foi escolhido aleatoriamente com igual probabilidade de 0 a p− 1 , independentemente dos outros.
Sua tarefa — encontre uma submatriz retangular desta tabela, na qual a soma é divisível por p. Entre todas essas submatrizes, você precisa encontrar aquela em que a soma dos elementos é máxima.
Formalmente, você precisa encontrar
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) que a soma de
ax,y sobre todos os
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) dividido em
p, e entre estes tem o valor máximo.
Entrada
A primeira linha contém três inteiros n, m, p (\(1 < ;= n m, p <= 1.000.000\)) — dimensões da matriz e o número pelo qual a soma da submatriz deve ser dividida.
As seguintes n linhas contêm m inteiros, o j-ésimo número na i-ésima linha é igual a ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
É garantido que cada número em a seja escolhido de forma independente e aleatória, equiprovavelmente de 0 a p−1.
Saída
Imprime um único inteiro — a soma máxima de uma submatriz retangular onde a soma é divisível por p. Se não houver nenhum, imprima 0.
Exemplos
| # |
Entrada |
Saída |
| 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 |