Problem
Die Katze Gans hat für Nick Fury eine rechteckige Tabelle a der Größe \(n \cdot m\) vorbereitet, die Zahlen von 0 bis p−1 enthält. Nick Fury erkannte sofort, dass jede Zahl in dieser Tabelle zufällig ausgewählt wurde, von 0 bis zu p−1 gleich ist, unabhängig von den anderen.
Ihre Aufgabe ist es, eine rechteckige Untermatrix dieser Tabelle zu finden, in der die Summe durch p geteilt wird.Unter all diesen Submatrizen muss man eine finden, in der die Summe der Elemente maximal ist.
Formal müssen Sie solche
\(1 <= i_1 <= i_2 <= n\) finden,
\(1 <= j_1 <= j_2 <= m\), dass die Summe von
ax,y für alle
\(1 <= j_1 <= j_2<= m\)ist, dass die Summe von
ax,y für alle
\(1 <=j_1<=j_2<=m\) -tex">\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) wird durch
p geteilt und hat die maximale Summe unter diesen.
Eingabe
In der ersten Zeile befinden sich drei ganze Zahlen n, m, p (\(1 <= n·m, p <= 1.000.000\)) der Matrixdimension und die Zahl, durch die die Summe der Untermatrix geteilt werden soll.
In den folgenden n Zeilen befinden sich m ganze Zahlen, jist die Zahl in der i-ten Zeile ist gleich ai,j (\(0 <= a_{i,j} <= p ? 1\)).
Es wird garantiert, dass jede Zahl in a unabhängig voneinander ausgewählt wird, ist zufällig von 0 bis zu p−1 gleich.
Ausgabe
Geben Sie eine ganze Zahl aus, — die maximale Summe einer rechteckigen Untermatrix, in der die Summe durch p geteilt wird. Wenn dies nicht der Fall ist, geben Sie 0 aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 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 |