Офицер космического десанта Сара оказалась с небольшим отрядом последователей на враждебной планете, полной представителей инопланетной расы зорков, отличающихся радикально экстремистскими взглядами в отношении представителей других рас. Сражаться с зорками было бы проявлением неуважения к их богатой культуре, так что она хочет как можно скорее окружить свою базу стеной, за которой можно будет в безопасности дожидаться обещанного командованием подкрепления.

Карта временно безопасного участка местности представляет собой клетчатое поле, состоящее из n горизонтальных рядов по m квадратов в каждом, причём база находится в c-м квадрате r-го ряда. Сара уже оценила, что для постройки стены в квадрате, находящемся в i-м ряду на j-й позиции, требуется a_i, j единиц времени. Сара считает, что если в некотором квадрате построена стена, то зорки не смогут пройти через него. Требуется построить стены так, чтобы зорки не смогли добраться до базы из-за пределов клетчатого поля, перемещаясь по клеткам, имеющим общую сторону, и не заходя при этом на клетки со стеной. На постройку всех стен должно быть затрачено как можно меньше единиц времени, учитывая, что стены строятся последовательно одна за другой, а между постройками стен в разных клетках время не тратится. Само собой, нельзя строить стену в клетке, в которой находится база Сары.

Сара задумалась, в каких именно клетках нужно построить стену, чтобы она удовлетворяла указанным требованиям. К счастью, в её отряде нашёлся программист, который взялся решить эту задачу.