28847번 - Кот Гусь и случайная матрица 다국어

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу $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$.