[ABC224H] Security Camera 2

给定两个点集, 左部点集有 $L$ 个点, 右部点集有 $R$ 个点, 在左部点的第 $i$ 个点上装摄像头需要 $A_i$ 的代价, 在右部点的第 $i$ 个点上装摄像头需要 $B_i$ 的代价, 一个点可以装多个摄像头. 求最小代价使得满足所有条件, 每个条件形如 $C_{i,j}$ , 表示左部点 $i$ 和右部点 $j$ 两点上的摄像头个数和至少为 $C_{i,j}$ .

[problemUrl]: https://atcoder.jp/contests/abc224/tasks/abc224_h 左側に $ 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} $

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

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 $ つもカメラを設置する必要がないケースもあります。