配点 : $600$ 点

問題文

左側に $L$ 個、右側に $R$ 個の頂点を有する二部グラフがあります。 高橋君は、この二部グラフの各頂点にカメラを設置することにしました。 カメラは $1$ 個設置するごとに以下に示す金額のコストが掛かります。

• $i$ $(1 \le i \le L)$ 番目の左側頂点に $1$ 個のカメラを設置するのに $A_i$ 円
• $j$ $(1 \le j \le R)$ 番目の右側頂点に $1$ 個のカメラを設置するのに $B_j$ 円

また、 $1$ つの頂点に複数個のカメラを設置してもよいです。

高橋君が以下の条件を満たすようにカメラを設置する時、必要な最小金額を求めてください。

• $1 \le i \le L, 1 \le j \le R$ を満たす全ての整数組 $(i,j)$ について、 $i$ 番目の左側頂点と $j$ 番目の右側頂点にカメラが合計で $C_{i,j}$ 個以上設置されている。

制約

• 入力は全て整数である
• $1 \le L,R \le 100$
• $1 \le A_i,B_i \le 10$
• $0 \le C_{i,j} \le 100$

入力

入力は以下の形式で標準入力から与えられる。

$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}$

出力

答えを整数として出力せよ。

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

37

以下のようにカメラを設置することで金額 $37$ 円を達成することができ、これが最小です。

• $1$ 番目の左側頂点にカメラを $2$ つ設置する。
• $2$ 番目の左側頂点にカメラを $3$ つ設置する。
• $3$ 番目の左側頂点にカメラを $2$ つ設置する。
• $1$ 番目の右側頂点にカメラを $1$ つ設置する。
• $3$ 番目の右側頂点にカメラを $1$ つ設置する。

1 1
10
10
0

0

$1$ つもカメラを設置する必要がないケースもあります。

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