Rectangle Painting
Seryozha wants to paint a rectangular table with m rows (numbered from 0 to m-1) and n columns (numbered from 0 to 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 2m + 2n - 2 diagonals. For instance, if m = 4 and n = 3, there are a total of 12 diagonals:
Input Data
The input consists of three lines:
The first line contains the numbers m and n.
The second line contains m+n-1 numbers, representing the cost of painting diagonals in the down-right direction. The i-th number (for i {1, ..., m+n-1}) corresponds to the diagonal where the difference between the row number and the column number is i-n. Thus, the first number refers to the diagonal consisting of only one cell at coordinates (0, n-1), the second number indicates the cost of painting the diagonal including cells (0, n-2) and (1, n-1), and so forth.
The third line contains m+n-1 numbers, representing the cost of painting diagonals in the up-right direction. The i-th number (for i {1, ..., m+n-1}) corresponds to the diagonal where the sum of the row number and the column number is 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 Data
Output the minimum cost required to paint the entire table.
Constraints
1 ≤ m ≤ 2 * 10^5
1 ≤ n ≤ 2 * 10^5
The cost of painting is an integer in the range [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:
