Пофарбування прямокутника#9050

Пофарбування прямокутника

1 секунда

64 мегабайти

Середня

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

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

Вхідні дані

Вхідні дані складаються з трьох рядків.Перший рядок містить числа $m$ і $n$ .Другий рядок містить $m + n - 1$ m+n-1 чисел, які задають вартість фарбування діагоналей у напрямку вниз вправо. $i$ -те число (при $i \in {1, \dots, m + n - 1}$ i \in \{1, \ldots, m+n-1\}) відноситься до діагоналі, в якій різниця номера рядка і номера стовпця дорівнює $i - n$ i-n. Таким чином, перше число відноситься до діагоналі, що складається тільки з однієї клітинки з координатами $(0, n - 1)$ (0, n-1) (рядок $0$ , стовпець $n - 1$ n-1), друге число визначає вартість фарбування діагоналі, що включає в себе клітинки $(0, n - 2)$ (0, n-2) і $(1, n - 1)$ (1, n-1), і так далі.Третій рядок містить $m + n - 1$ m+n-1 чисел, які визначають вартість фарбування діагоналей у напрямку вгору вправо. $i$ -те число (при $i \in {1, \dots, m + n - 1}$ i \in \{1, \ldots, m+n-1\}) відноситься до діагоналі, в якій сума номера рядка і номера стовпця дорівнює $i - 1$ i-1. Таким чином, перше число відноситься до діагоналі, що складається тільки з однієї клітинки з координатами $(0, 0)$ , друге число визначає вартість фарбування діагоналі, що включає в себе клітинки $(1, 0)$ і $(0, 1)$ , і так далі.

Вихідні дані

Виведіть мінімальну вартість фарбування всієї таблиці.

Приклади

Приклад 1

Приклад 2

Примітка

Обмеження

$1 \leq m \leq 2 \cdot 1 0^{5}$ 1 \le m \le 2 \cdot 10^5
$1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5
Вартість фарбування — цілі числа в інтервалі $[1, 1 0^{9}]$ [1, 10^9]

Пояснення до першого прикладу

У цьому прикладі для мінімізації вартості повинні бути пофарбовані наступні діагоналі:

Фарбування кожної з цих діагоналей коштує $1$ , відповідно підсумкова вартість дорівнює $4$ .

Пояснення до другого прикладу

У цьому випадку мінімальна вартість виходить фарбуванням наступних діагоналей вартістю $3$ , $2$ , $3$ , $3$ , $1$ і $2$ відповідно: