Пофарбування прямокутника
Сергій хоче пофарбувати прямокутну таблицю, що складається з m рядків (пронумерованих від 0 до m-1) і n стовпців (пронумерованих від 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 відповідно:
