Cat Goose and the Random Matrix

Cat Goose prepared a rectangular table $a$ of size $n \times m$ for Nick Fury. Each entry is an integer from $0$ to $p-1$.

Nick Fury immediately realized that every number in the table was chosen uniformly at random from $0$ to $p-1$, independently of the others.

Find a rectangular submatrix of the table whose sum is divisible by $p$, and among all such submatrices, output the one with the largest sum. Formally, find $1 \leq i_1 \leq i_2 \leq n$ and $1 \leq j_1 \leq j_2 \leq m$ such that the sum of $a_{x,y}$ over $i_1 \leq x \leq i_2$ and $j_1 \leq y \leq j_2$ is divisible by $p$, and this sum is maximal among all such submatrices.

The first line contains three integers $n$, $m$, $p$ ($1 \leq n \cdot m, p \leq 1\,000\,000$): the table dimensions and the number that the submatrix sum must be divisible by.

Each of the next $n$ lines contains $m$ integers, where the $j$-th number in the $i$-th line is $a_{i,j}$ ($0 \leq a_{i,j} \leq p - 1$).

It is guaranteed that every number in $a$ was chosen independently and uniformly at random from $0$ to $p-1$.

Print one integer: the maximum sum of a rectangular submatrix whose sum is divisible by $p$. If no such submatrix exists, print $0$.