Задача №111532. Уголки
После почти повсеместного закрытия казино у нас в стране, предприимчивые дельцы стали создавать клубы по игре в различные азартные, но пока еще не запрещенные игры. Одной из таких игр стала игра «Уголки».
Игроку выдается карточка, на которой нарисована таблица, состоящая из M строк и N столбцов, каждым элементом которой является целое число. Строки и столбцы пронумерованы, начиная с единицы, клетка с номером (1, 1) находится в левом верхнем углу.
Игрок может сделать несколько ходов по следующим правилам. Первым ходом он может указать на любой элемент таблицы (r1, c1), и все числа в прямоугольнике (1, 1)–(r1, c1) меняют свой знак на противоположный. Здесь первое число обозначает номер строки, а второе — номер столбца. Следующие ходы игрока аналогичны, то есть выбирается прямоугольник (1, 1)–(ri, ci) и все числа опять меняют знак, однако каждый следующий прямоугольник должен полностью содержать предыдущий выбранный, но не совпадать с ним. Количество ходов при этом естественным образом ограничено размерами таблицы. При желании ходы можно и не выполнять совсем.
Например, если таблица состоит из 10 строк и 9 столбцов, то возможна в том числе такая последовательность ходов: (2, 2)–(4, 4)–(4, 6)–(5, 6).
После того как все желаемые ходы выполнены, подсчитывается результат игры — сумма значений элементов преобразованной таблицы. Если сумма положительная, то игрок получает от заведения соответствующую сумму денег, а если отрицательная — платит ее.
Помогите игроку добиться наилучшего результата: выиграть как можно больше или хотя бы проиграть как можно меньше.
В первой строке входного файла заданы два натуральных числа M и N (M ≤ 1 000, N ≤ 1 000). Каждая из следующих M строк содержит N целых чисел, по модулю не превышающих 1 000, — элементы таблицы.
В первой строке выходного файла выведите максимальную сумму, которую можно получить с помощью оптимальной стратегии игры по описанным правилам. Во второй строке выведите целое число K — количество действий в алгоритме, дающем наилучший результат. В следующих K строках выведите последовательность из K пар чисел (ri, ci), описывающих сам алгоритм.
Если дающих наилучший результат алгоритмов несколько, выведите любой.
2 3
3 6 4
1 -2 -7
21
2
1 3
2 3
4 4
2 -1 -5 -1
1 -3 -3 -1
0 -5 1 1
-1 -1 0 2
22
2
2 1
4 3
Тесты состоят из четырех групп.
- Тесты 1–2, из условия, оцениваются в 0 баллов.
- В тестах этой группы M = 1, 1 ≤ N ≤ 1 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ M ≤ 100, 1 ≤ N ≤ 100. Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
- Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый тест оценивается независимо от других.