|
Кот Гусь и случайная матрица
Куча
Префиксные суммы(минимумы, ...)
Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера n × m, содержащую числа от 0 до p − 1.
Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p − 1, независимо от остальных.
Ваша задача — найти прямоугольную подматрицу этой таблицы, в которой сумма делится на p.
Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.
Формально, вам необходимо найти такие 1 <= i1 <= i2 <= n, 1 <= j1 <= j2 <= m, что сумма ax,y по всем i1 <= x <= i2, j1 <= y <= j2 делится на p, и среди таких имеет максимальную сумму.
Формат входных данных
В первой строке входного файла расположено три целых числа n, m, p (1 <= n·m, p <= 1 000 000) — размерности матрицы и число, на которое должна делится сумма подматрицы.
В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно ai,j (0 <= ai,j <= p − 1).
Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.
Формат выходных данных
Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p.
Если таких нет, выведите 0.
|
Ввод |
Вывод |
|
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 |
|