H - Security Camera 2

Score : $600$ points

Problem Statement

We have a bipartite graph with $L$ vertices to the left and $R$ vertices to the right.
Takahashi will install surveillance cameras in these vertices.
Installing cameras incurs the following cost.

• $A_i$ yen (the Japanese currency) for each camera installed in the $i$-th $(1 \le i \le L)$ vertex to the left;
• $B_j$ yen (the Japanese currency) for each camera installed in the $j$-th $(1 \le j \le R)$ vertex to the right.

It is allowed to install multiple cameras on the same vertex.

Find the minimum amount of money needed to install cameras to satisfy the following condition.

• For every pair of integers $(i, j)$ such that $1 \le i \le L, 1 \le j \le R$, there is a total of $C_{i,j}$ or more cameras installed in the $i$-th vertex to the left and $j$-th vertex to the right.

Constraints

• All values in input are integers.
• $1 \le L,R \le 100$
• $1 \le A_i,B_i \le 10$
• $0 \le C_{i,j} \le 100$

Input

Input is given from Standard Input in the following format:

$L$ $R$

$A_1$ $A_2$ $\dots$ $A_L$

$B_1$ $B_2$ $\dots$ $B_R$

$C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,R}$

$C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,R}$

$\vdots$

$C_{L,1}$ $C_{L,2}$ $\dots$ $C_{L,R}$

Output

Print the answer as an integer.

3 4
4 3 6
5 2 3 4
1 2 3 2
2 1 2 3
3 2 1 2

37

You can achieve the objective for $37$ yen as follows, which is the minimum amount required.

• Install $2$ cameras on the $1$-st vertex in the left.
• Install $3$ cameras on the $2$-nd vertex in the left.
• Install $2$ cameras on the $3$-rd vertex in the left.
• Install $1$ camera on the $1$-st vertex in the right.
• Install $1$ camera on the $3$-rd vertex in the right.

1 1
10
10
0

0

No camera may be needed.

5 6
3 2 6 7 5
4 9 8 6 2 3
2 0 2 1 1 0
2 3 2 1 0 0
2 2 4 0 2 2
4 1 0 3 0 2
1 0 0 2 2 5

79