Задача Не курите

Описание

После принятия закона о запрете курения, владелец ресторана Ануар решил разбить свой ресторан на две зоны – курящий зал и некурящий зал.

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

Ануар хочет закрыть некоторые проходы пластиковыми окнами, так, чтобы ресторан был разбит на две зоны. При этом курящая зона должна быть соединена с выходом, а некурящая зона с кухней. Для удобства на каждом пластиковом окне должно быть закрываемое отверстие размером 1 кв. м. для передачи пищи из некурящей зоны в курящую.

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

Формат входных данных

Первая строка входного файла содержит два положительных числа nr, nc < 1000 – размеры ресторана. (всего в ресторане nr * nc комнат).

Следующие два числа 0<=er<nr, 0<=ec<nc, координаты комнаты, соединенной с выходом.

Следующие два числа 0<=kr<nr, 0<=kc<nc, координаты комнаты, соединенной с кухней.

Следующие nr строк содержат nc-1 положительных чисел, каждая из которых меньше 100. Число на позиции j строки i характеризует размер прохода в квадратных метрах между комнатами (i,j) и (i, j+1)

Следующие nr-1 строк содержат nc положительных чисел, каждая из которых меньше 100. Число на позиции j строки i характеризует размер прохода в квадратных метрах между комнатами (i,j) и (i+1, j)

Формат выходных данных

В выходной файл выведите единственное число – минимальную стоимость затрат для разделения ресторана на две зоны.