Your are playing a computer game. The game is played on a chessboard of 
rows and 
columns.
For each grid on the board, you can choose to put a black piece or a white piece on it, or leave it blank. Denote &preview=true)
as the grid in the 
-th row and the 
-column. For each 
, putting a black piece on earns you 
points, while a white piece earns you 
points, and leaving blank do not affect your score. The overall score will be the sum of the points earned by each piece. Note that a grid can contain at most one piece at the same time, that is, you cannot put a white piece and a black one simultaneously. It is guaranteed that , are all non-negative integers.
After you finish placing the pieces, the computer program checks whether the pieces are put in a \textbf{beautiful} way or not. Let's define 
as the number of black pieces in the -th row, 
as the number of black pieces in the -th column, 
as the number of white pieces in the -th row, and 
as the number of white pieces in the -th column. The pieces are considered \textbf{beautiful} if
- For any
, 
holds. - For any
, 
holds.
Tired of high scores, you decide to minimize your score. To simplify the problem, you only need to output the minimum possible score among all beautiful placements of pieces.
输入描述:
he first line of input contains two integers &preview=true)
, denoting the number of rows and columns of the board.
The next lines describe the points earned by putting black pieces. The -th of them contains integers, the -th of which denotes &preview=true)
.
The next lines describe the points earned by putting white pieces. The -th of them contains integers, the -th of which denotes &preview=true)
.
The next lines describe the constraints on each row, the -th of which contains two integers &preview=true)
, whose meaning can be found in the statement above.
The next lines describe the constraints on each column, the -th of which contains two integers &preview=true)
, whose meaning can be found in the statement above.
It is guaranteed that there exists at least one strategy that satisfies all the constraints.
输出描述:
Output a single integer, denoting the minimum score you can get.
示例1
输入
复制
3 3
6 9 0
3 2 7
6 4 6
0 6 5
1 6 9
8 5 7
-3 -1
-3 0
1 3
0 0
1 1
-2 0