РОИ: 2 тур

На всемирной олимпиаде роботов проводятся соревнования по робогольфу. Поле, на котором происходит игра, имеет вид прямоугольника, состоящего из \(n \times m\) единичных квадратов. Строки поля пронумерованы числами от \(1\) до \(n\), а столбцы — от \(1\) до \(m\). Таким образом, каждый квадрат характеризуется двумя положительными целыми числами \(r\) и \(c\) — номерами строки и столбца, на пересечении которых он находится.

Два робота по очереди перемещают специальную фишку по полю, в некоторых квадратах которого находятся ловушки. Если фишка находится в квадрате \((r, c)\), то робот, выполняющий очередной ход, может переместить её в квадрат \((r + 1, c)\) или в квадрат \((r, c + 1)\). Если соответствующего квадрата не оказалось, поскольку фишка находится в последней строке или в последнем столбце поля, робот может переместить её за границу поля. Игра заканчивается в том случае, когда фишка оказывается либо за границей поля, либо в квадрате с ловушкой.

Каждой ловушке соответствует некоторое целое число \(v_i\) — её цена . Результат игры равен значению цены ловушки, в которой закончилась игра, или равен 0, если фишка оказалась за границей поля. Робот, который делает ход первым, стремится минимизировать результат игры, а робот, который делает ход вторым — максимизировать.

Пусть фишка вначале находится в квадрате \((r, c)\). Гарантированный результат игры \(g(r, c)\) для этого квадрата равен минимальному возможному результату игры, которого может добиться делающий первый ход робот вне зависимости от действий соперника. Поскольку стартовый квадрат до начала матча неизвестен, разработчики роботов хотят вычислить сумму значений \(g(r, c)\) для всех квадратов поля.

Требуется написать программу, которая по заданным расположениям и ценам ловушек определит сумму гарантированных результатов игры по всем квадратам поля.