Кот Гусь и случайная матрица

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу $a$ размера $n \times m$, содержащую числа от $0$ до $p-1$.

Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от $0$ до $p-1$, независимо от остальных.

Ваша задача --- найти прямоугольную подматрицу этой таблицы, в которой сумма делится на $p$. Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.

Формально, вам необходимо найти такие $1 \leq i\_1 \leq i\_2 \leq n$, $1 \leq j\_1 \leq j\_2 \leq m$, что сумма $a\_{x, y}$ по всем $i\_1 \leq x \leq i\_2, j\_1 \leq y \leq j\_2$ делится на $p$, и среди таких имеет максимальную сумму.

В первой строке входного файла расположено три целых числа $n, m, p$ ($1 \leq n \cdot m, p \leq 1\\,000\\,000$) --- размерности матрицы и число, на которое должна делится сумма подматрицы.

В следующих $n$ строках расположено по $m$ целых чисел, $j$-е число в $i$-й строке равно $a\_{i, j}$ ($0 \leq a\_{i, j} \leq p - 1$).

Гарантируется, что каждое число в $a$ выбрано независимо случайно равновероятно от $0$ до $p-1$.

Выведите одно целое число --- максимальную сумму прямоугольной подматрицы, в которой сумма делится на $p$.

Если таких нет, выведите $0$.