题目描述

左側に $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}$ 個以上設置されている。

输入格式

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

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

输出格式

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

题目大意

给定两个点集, 左部点集有 $L$ 个点, 右部点集有 $R$ 个点, 在左部点的第 $i$ 个点上装摄像头需要 $A_i$ 的代价, 在右部点的第 $i$ 个点上装摄像头需要 $B_i$ 的代价, 一个点可以装多个摄像头.

求最小代价使得满足所有条件, 每个条件形如 $C_{i,j}$ , 表示左部点 $i$ 和右部点 $j$ 两点上的摄像头个数和至少为 $C_{i,j}$ .

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

37

1 1
10
10
0

0

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

提示

制約

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

Sample Explanation 1

以下のようにカメラを設置することで金額 $37$ 円を達成することができ、これが最小です。 - $1$ 番目の左側頂点にカメラを $2$ つ設置する。 - $2$ 番目の左側頂点にカメラを $3$ つ設置する。 - $3$ 番目の左側頂点にカメラを $2$ つ設置する。 - $1$ 番目の右側頂点にカメラを $1$ つ設置する。 - $3$ 番目の右側頂点にカメラを $1$ つ設置する。

Sample Explanation 2

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