Покраска прямоугольника
Сережа хочет покрасить прямоугольную таблицу,состояющую из m строк (пронумерованных от 0 до m-1 ) и столбцов (пронумерованных 0 от до n-1).Изначально все клетки таблицы белые.На каждом шаге он выбирает какую-то диагональ (см.Пример 2) и закрашивает все клетки на этой диагонали в свой любимый цвет.Однако стоимость покраски некоторых диагоналей может быть дороже других,вне зависимости от их длины.По заданной стоимости покраски каждой из диагоналей определите минимальную общую стоимость покраски всех клеток в таблице. Обратите внимание,что клетки можно перекрашивать дважды.
Прямоугольная сетка из m строк и n столбцов имеет 2m+2n-2 диагоналей .Например,если m = 4 и n = 3 ,то всего существует 12 диагоналей:
####Входные данныеВходные данные состоят из трех строк.Первая строка содержит числа m и n .Вторая строка содержит m+n-1 чисел,которые задают стоимость покраски диагоналей по направлению вниз вправо .i-е число (при i {1,....,m+n-1}) относится к диагонали,в которой разность номера строки и номера столбца равна i-n.Таким образом первое число относится к диагонали,состоящей только из одной клетки с координатами(0,n-1) (строка 0,столбец n-1),второе число определяет стоимость покраски диагонали включающей в себя клетки (0,n-2) и (1,n-1),и т.д .Третья строка содержит m+n-1 чисел,которые определяют стоимость покраски диагоналей по направлению вверх вправо .i-е число (при i {1,...,m+n-1})относится к диагонали,в которой сумма номера строки и номера столбца равна i-1.Таким образом,первое число относится к диагонали,состоящей только из одной клетки с координатами (0,0),второе число определяет стоимость покраски диагонали включающей в себя клетки (1,0) и (0,1), и т.д.
####Выходные данныеВыведите минимальную стоимость покраски всей таблицы.
####Ограничения
(1 ≤ m ≤ 2 *
10^5)(1 ≤ n ≤ 2 *
10^5)Стоимость покраски - целые числа в интервале [1,
10^9]
####Пояснение к первому примеру
В этом примере для минимизации стоимости должны быть покрашены следующие диагонали:
Покраска каждой из этих диагоналей стоит 1, соответственно итоговая стоимость равна 4.
####Пояснение ко второму примеру
В этом случае минимальная стоимость получается покраской следующих диагоналей стоимостью 3,2,3,3,1 и 2 соответственно:
