Problem
Cat Goose a préparé pour Nick Fury un tableau rectangulaire a de taille \(n \cdot m\) contenant des nombres de 0< /span> code> à p−1. Nick Fury s'est immédiatement rendu compte que chaque nombre de ce tableau était choisi au hasard avec une probabilité égale de 0 à p− 1 , indépendamment des autres.
Votre tâche — trouver une sous-matrice rectangulaire de ce tableau, dans laquelle la somme est divisible par p. Parmi toutes ces sous-matrices, vous devez trouver celle dans laquelle la somme des éléments est maximale.
Formellement, vous devez trouver
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) que la somme de
ax,y sur tout
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) divisé sur
p, et parmi ceux-ci a le montant maximum.
Entrée
La première ligne contient trois entiers n, m, p (\(1 < ;= n m, p <= 1 000 000\)) — dimensions de la matrice et le nombre par lequel la somme de la sous-matrice doit être divisée.
Les lignes n suivantes contiennent des entiers m, le j-ème nombre dans la i-ème ligne est égal à ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
Il est garanti que chaque nombre dans a est choisi indépendamment au hasard, équiprobablement de 0 à p−1.
Sortie
Afficher un seul entier — la somme maximale d'une sous-matrice rectangulaire où la somme est divisible par p. S'il n'y en a pas, écrivez 0.
Exemples
| # |
Entrée |
Sortie |
| 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 |