Rectangle Painting#9050

Rectangle Painting

1 second

64 megabytes

Medium

Seryozha wants to paint a rectangular table with $m$ rows (numbered from $0$ to $m - 1$ m-1) and $n$ columns (numbered from $0$ to $n - 1$ n-1). Initially, all the cells in the table are white. In each step, he selects a diagonal (refer to Example $2$ ) and paints all the cells on that diagonal in his favorite color. The cost of painting a diagonal can vary, regardless of its length. Given the cost of painting each diagonal, determine the minimum total cost to paint all the cells in the table. Note that cells can be painted more than once.

A rectangular grid with $m$ rows and $n$ columns has $2 m + 2 n - 2$ 2m + 2n - 2 diagonals. For instance, if $m = 4$ m = 4 and $n = 3$ n = 3, there are a total of $12$ diagonals:

Input

The input consists of three lines.The first line contains the numbers $m$ and $n$ .The second line contains $m + n - 1$ m+n-1 numbers, representing the cost of painting diagonals in the down-right direction. The $i$ -th number (for $i \in {1, \dots, m + n - 1}$ i \in \{1, \ldots, m+n-1\}) corresponds to the diagonal where the difference between the row number and the column number is $i - n$ i-n. Thus, the first number refers to the diagonal consisting of only one cell at coordinates $(0, n - 1)$ (0, n-1) (row $0$ , column $n - 1$ n-1), the second number indicates the cost of painting the diagonal including cells $(0, n - 2)$ (0, n-2) and $(1, n - 1)$ (1, n-1), and so forth.The third line contains $m + n - 1$ m+n-1 numbers, representing the cost of painting diagonals in the up-right direction. The $i$ -th number (for $i \in {1, \dots, m + n - 1}$ i \in \{1, \ldots, m+n-1\}) corresponds to the diagonal where the sum of the row number and the column number is $i - 1$ i-1. Thus, the first number refers to the diagonal consisting of only one cell at coordinates $(0, 0)$ , the second number indicates the cost of painting the diagonal including cells $(1, 0)$ and $(0, 1)$ , and so forth.

Output

Output the minimum cost required to paint the entire table.

Examples

Example 1

Example 2

Note

Constraints

$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
The cost of painting is an integer in the range $[1, 1 0^{9}]$ [1, 10^9]

Explanation for the first example

In this example, to achieve the minimum cost, the following diagonals should be painted:

The cost of painting each of these diagonals is $1$ , resulting in a total cost of $4$ .

Explanation for the second example

In this case, the minimum cost is achieved by painting the following diagonals with costs $3$ , $2$ , $3$ , $3$ , $1$ , and $2$ respectively: