H - Security Camera 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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}

出力

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

入力例 1

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

出力例 1

37

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

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

入力例 2

1 1
10
10
0

出力例 2

0

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

入力例 3

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

出力例 3

79

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.

Sample Input 1

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

Sample Output 1

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.

Sample Input 2

1 1
10
10
0

Sample Output 2

0

No camera may be needed.

Sample Input 3

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

Sample Output 3

79