Задача №114886. Кот Гусь и случайная матрица

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

Система оценки

Эта задача состоит из пяти подзадач. Для некоторых подзадач выполняются дополнительные ограничения, указанные в таблице ниже.

Подзадача Количество тестов Дополнительные ограничения Необходимые подзадачи
1 5 \(n \cdot m \leq 3000\)
2 5 \(n, m \leq 300\)
3 5 \(n = 1\) или \(m = 1\)
4 5 \(p \leq 5000\)
5 30 1, 2, 3, 4

Примеры
Входные данные
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
Сдать: для сдачи задач необходимо войти в систему