Minimum Diagonal Coloring Cost

Srečko has an (m \times n) grid with rows numbered from (0) to (m-1) and columns numbered from (0) to (n-1). Initially, every cell is white. In each step he chooses a diagonal and colors every cell on that diagonal. There are two kinds of diagonals in the grid: the NW-SE diagonals (with constant (d=i-j)) and the NE-SW diagonals (with constant (s=i+j)). Note that the grid has a total of (2(m+n-1)=2n+2m-2) diagonals. Each diagonal has an associated coloring cost (which does not depend on its length), and the same cell may be recolored several times. Your task is to choose a subset of diagonals such that every cell is colored (i.e. for every cell ((i,j)), at least one of its two diagonals is chosen) and the total cost is minimized. (\newline)(\newline)Hint: For a cell ((i,j)) the two diagonals are given by the values (d=i-j) and (s=i+j). In this problem, you are given the cost for each NW-SE diagonal and each NE-SW diagonal. You can model the problem as a weighted bipartite vertex cover problem on a bipartite graph where one part corresponds to NW-SE diagonals and the other to NE-SW diagonals. An edge exists between a NW-SE diagonal (with value (d)) and a NE-SW diagonal (with value (s)) if and only if the cell ((i,j)) with (i=\frac{s+d}{2}) and (j=\frac{s-d}{2}) is inside the grid (which requires (s+d) to be even and (0 \leq i < m,; 0 \leq j < n)). The answer is the minimum cost of a vertex cover in this bipartite graph, and it can be computed via a minimum cut formulation.

inputFormat

The input begins with two integers (m) and (n) (the number of rows and columns).\n\nThe next line contains (m+n-1) integers representing the costs of the NW-SE diagonals. These diagonals correspond to values of (d=i-j) in increasing order starting from (d=-(n-1)) up to (d=m-1).\n\nThe following line contains (m+n-1) integers representing the costs of the NE-SW diagonals. These diagonals correspond to values of (s=i+j) in increasing order from (0) to (m+n-2).

outputFormat

Output a single integer: the minimum total cost needed to color every cell in the grid.

sample

2 2
1 2 3
3 2 1

4