Problem
Angsa Kucing menyediakan meja segi empat tepat a untuk Nick Fury bersaiz \(n \cdot m\) yang mengandungi nombor daripada 0< /span> kod> kepada p&tolak;1. Nick Fury serta-merta menyedari bahawa setiap nombor dalam jadual ini dipilih secara rawak dengan kebarangkalian yang sama daripada 0 hingga p&tolak; 1 , tanpa mengira yang lain.
Tugas anda — cari submatriks segi empat tepat bagi jadual ini, di mana jumlahnya boleh dibahagikan dengan p. Antara semua submatriks sedemikian, anda perlu mencari submatriks yang jumlah unsurnya adalah maksimum.
Secara rasmi, anda perlu mencari
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) bahawa jumlah
ax,y ke atas semua
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) berpecah pada
p, dan antara ini mempunyai jumlah maksimum.
Input
Baris pertama mengandungi tiga integer n, m, p (\(1 < ;= n m, p <= 1,000,000\)) — dimensi matriks dan nombor yang mana jumlah submatriks harus dibahagikan.
Baris n berikut mengandungi integer m, nombor ke-j dalam baris i- sama dengan ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
Dijamin bahawa setiap nombor dalam a dipilih secara bebas secara rawak, sama ada daripada 0 hingga p&tolak;1.
Output
Cetak satu integer — jumlah maksimum submatriks segi empat tepat yang jumlahnya boleh dibahagi dengan p. Jika tiada, cetak 0.
Contoh
| # |
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 |