eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Покраска прямоугольника

Покраска прямоугольника

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Сережа хочет покрасить прямоугольную таблицу,состояющую из m строк (пронумерованных от 0 до m-1 ) и столбцов (пронумерованных 0 от до n-1).Изначально все клетки таблицы белые.На каждом шаге он выбирает какую-то диагональ (см.Пример 2) и закрашивает все клетки на этой диагонали в свой любимый цвет.Однако стоимость покраски некоторых диагоналей может быть дороже других,вне зависимости от их длины.По заданной стоимости покраски каждой из диагоналей определите минимальную общую стоимость покраски всех клеток в таблице. Обратите внимание,что клетки можно перекрашивать дважды.

Прямоугольная сетка из m строк и n столбцов имеет 2m+2n-2 диагоналей .Например,если m = 4 и n = 3 ,то всего существует 12 диагоналей:

Screenshot from 2019-12-28 11-22-37.png

####Входные данныеВходные данные состоят из трех строк.Первая строка содержит числа 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]

####Пояснение к первому примеру

В этом примере для минимизации стоимости должны быть покрашены следующие диагонали:

Screenshot from 2019-12-28 11-41-00.png

Покраска каждой из этих диагоналей стоит 1, соответственно итоговая стоимость равна 4.

####Пояснение ко второму примеру

В этом случае минимальная стоимость получается покраской следующих диагоналей стоимостью 3,2,3,3,1 и 2 соответственно:

Screenshot from 2019-12-28 11-45-15.png

Приклад

Вхідні дані #1
2 2
1 3 1
1 3 1
Вихідні дані #1
4
Вхідні дані #2
4 3
2 3 9 3 4 3
2 3 3 1 2 4
Вихідні дані #2
14
Джерело EJOI 2019 Day2