

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