Problem
Cat Goose ha preparato per Nick Fury un tavolo rettangolare a di dimensioni \(n \cdot m\) contenente numeri da 0< /span> code> a p−1. Nick Fury si rese immediatamente conto che ogni numero in questa tabella era stato scelto a caso con uguale probabilità da 0 a p− 1 , indipendentemente dagli altri.
Il tuo compito — trova una sottomatrice rettangolare di questa tabella, in cui la somma è divisibile per p. Tra tutte queste sottomatrici, devi trovare quella in cui la somma degli elementi è massima.
Formalmente, devi trovare
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) che la somma di
ax,y su tutto
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) diviso su
p, e tra questi ha l'importo massimo.
Input
La prima riga contiene tre numeri interi n, m, p (\(1 < ;= n m, p <= 1.000.000\)) — dimensioni della matrice e il numero per cui dividere la somma della sottomatrice.
Le seguenti n righe contengono m numeri interi, il j-esimo numero nella i-esima riga uguale a ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
È garantito che ogni numero in a sia scelto indipendentemente a caso, equiprobabilmente da 0 a p−1.
Uscita
Stampa un singolo numero intero — la somma massima di una sottomatrice rettangolare dove la somma è divisibile per p. Se non ce ne sono, stampa 0.
Esempi
| # |
Input |
Uscita |
| 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 |