E - フリーマーケットの割り当て 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君はフリーマーケットに出店し、M 個の商品を販売しようとしています。商品にはそれぞれ 1 から M の番号が付いており、商品 j の仕入れ値は C_j 円です。売れ残った商品は仕入れ元に返品できるため、売れ残りによる損失は発生しません。

フリーマーケットには N 人の来場者が訪れます。来場者にはそれぞれ 1 から N の番号が付いています。来場者 i は、商品 j に対して最大 V_{i,j} 円まで支払ってもよいと考えています（これを来場者 i の商品 j に対する評価額と呼びます）。

高橋君は各来場者の評価額を事前に把握しており、各商品を評価額と同額の価格で売ります。すなわち、商品 j を来場者 i に売る場合、売値は V_{i,j} 円となり、その取引から得られる利益は V_{i,j} - C_j 円です。

高橋君は、以下の条件をすべて満たすように商品の売り先を決めます。

  • 各商品は 1 個しかないため、1 つの商品を 2 人以上の来場者に売ることはできない。すなわち、各商品について、売る相手を 1 人だけ選ぶか、誰にも売らないかのいずれかである。
  • 各来場者は最大 1 つの商品しか購入しない。すなわち、各来場者について、購入する商品を 1 つだけ選ぶか、何も購入しないかのいずれかである。
  • 利益が負になる取引は行わない。すなわち、商品 j を来場者 i に売るためには V_{i,j} \geq C_j でなければならない。

これらの条件のもとで、高橋君が得られる利益の合計の最大値を求めてください。なお、どの商品も売らないという選択も可能であり、その場合の利益の合計は 0 です。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 14
  • N \times M \leq 2 \times 10^5
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • 0 \leq V_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
  • 入力はすべて整数である。

入力

N M
C_1 C_2 \ldots C_M
V_{1,1} V_{1,2} \ldots V_{1,M}
V_{2,1} V_{2,2} \ldots V_{2,M}
\vdots
V_{N,1} V_{N,2} \ldots V_{N,M}
  • 1 行目には、来場者の人数を表す整数 N と、商品の個数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各商品の仕入れ値を表す整数 C_1, C_2, \ldots, C_M が、スペース区切りで与えられる。
  • 続く N 行にわたり、各来場者の各商品に対する評価額が与えられる。
  • 第 i+2 行 (1 \leq i \leq N) には、来場者 i の商品 1, 2, \ldots, M に対する評価額を表す整数 V_{i,1}, V_{i,2}, \ldots, V_{i,M} が、スペース区切りで与えられる。

出力

高橋君が得られる利益の合計の最大値を 1 行で出力せよ。

入力例 1

3 2
5 4
8 3
6 10
4 7

出力例 1

9

入力例 2

2 3
100 200 300
50 150 250
99 199 299

出力例 2

0

入力例 3

8 5
10 20 15 8 30
12 18 20 7 35
9 25 14 10 29
30 10 18 8 31
11 22 16 20 10
5 19 40 9 32
13 21 15 8 30
50 5 5 5 5
10 20 15 100 60

出力例 3

167

入力例 4

20 12
40 25 60 10 75 55 30 90 15 50 65 20
100 20 70 9 80 54 33 95 15 55 70 22
39 40 61 12 74 100 31 20 18 49 66 25
45 30 59 30 76 56 80 91 10 52 64 19
10 25 100 11 75 54 29 120 16 50 63 21
41 26 60 10 200 55 30 90 15 50 65 20
80 24 58 9 74 53 32 89 14 120 64 18
42 100 62 13 73 57 28 88 17 51 90 30
40 25 60 10 75 55 30 90 15 50 65 20
0 0 0 0 0 0 0 0 0 0 0 0
60 45 80 25 90 70 50 110 35 75 85 40
38 27 65 8 78 52 35 93 20 48 67 22
90 10 10 10 10 10 10 10 10 10 10 10
20 60 20 60 20 60 20 60 20 60 20 60
55 35 75 15 85 65 45 105 25 70 80 30
43 28 63 14 77 58 34 92 19 53 68 24
70 70 70 70 70 70 70 70 70 70 70 70
41 24 59 11 76 56 29 91 16 51 66 23
120 130 140 150 160 170 180 190 200 210 220 230
5 200 5 200 5 200 5 200 5 200 5 200
44 29 64 13 79 59 36 94 21 54 69 26

出力例 4

955

入力例 5

1 1
1000000000
1000000000

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is opening a stall at a flea market and plans to sell M items. The items are numbered 1 through M, and the cost price of item j is C_j yen. Unsold items can be returned to the supplier, so no loss is incurred from unsold items.

There are N visitors to the flea market, numbered 1 through N. Visitor i is willing to pay up to V_{i,j} yen for item j (this is called visitor i's valuation of item j).

Takahashi knows each visitor's valuation in advance and sells each item at a price equal to the valuation. That is, if item j is sold to visitor i, the selling price is V_{i,j} yen, and the profit obtained from this transaction is V_{i,j} - C_j yen.

Takahashi decides the buyers of the items so that all of the following conditions are met:

  • Since there is only 1 of each item, a single item cannot be sold to 2 or more visitors. That is, for each item, he either chooses at most one buyer or sells it to no one.
  • Each visitor purchases at most 1 item. That is, for each visitor, they either choose at most one item to purchase or purchase nothing.
  • No transaction with a negative profit is made. That is, to sell item j to visitor i, it must hold that V_{i,j} \geq C_j.

Under these conditions, find the maximum possible total profit Takahashi can obtain. Note that it is possible to choose not to sell any items, in which case the total profit is 0.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 14
  • N \times M \leq 2 \times 10^5
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • 0 \leq V_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
  • All input values are integers.

Input

N M
C_1 C_2 \ldots C_M
V_{1,1} V_{1,2} \ldots V_{1,M}
V_{2,1} V_{2,2} \ldots V_{2,M}
\vdots
V_{N,1} V_{N,2} \ldots V_{N,M}
  • The first line contains the integer N, representing the number of visitors, and the integer M, representing the number of items, separated by a space.
  • The second line contains the integers C_1, C_2, \ldots, C_M, representing the cost prices of the items, separated by spaces.
  • The following N lines provide each visitor's valuation for each item.
  • The (i+2)-th line (1 \leq i \leq N) contains the integers V_{i,1}, V_{i,2}, \ldots, V_{i,M}, representing visitor i's valuations for items 1, 2, \ldots, M, separated by spaces.

Output

Print the maximum possible total profit Takahashi can obtain in a single line.

Sample Input 1

3 2
5 4
8 3
6 10
4 7

Sample Output 1

9

Sample Input 2

2 3
100 200 300
50 150 250
99 199 299

Sample Output 2

0

Sample Input 3

8 5
10 20 15 8 30
12 18 20 7 35
9 25 14 10 29
30 10 18 8 31
11 22 16 20 10
5 19 40 9 32
13 21 15 8 30
50 5 5 5 5
10 20 15 100 60

Sample Output 3

167

Sample Input 4

20 12
40 25 60 10 75 55 30 90 15 50 65 20
100 20 70 9 80 54 33 95 15 55 70 22
39 40 61 12 74 100 31 20 18 49 66 25
45 30 59 30 76 56 80 91 10 52 64 19
10 25 100 11 75 54 29 120 16 50 63 21
41 26 60 10 200 55 30 90 15 50 65 20
80 24 58 9 74 53 32 89 14 120 64 18
42 100 62 13 73 57 28 88 17 51 90 30
40 25 60 10 75 55 30 90 15 50 65 20
0 0 0 0 0 0 0 0 0 0 0 0
60 45 80 25 90 70 50 110 35 75 85 40
38 27 65 8 78 52 35 93 20 48 67 22
90 10 10 10 10 10 10 10 10 10 10 10
20 60 20 60 20 60 20 60 20 60 20 60
55 35 75 15 85 65 45 105 25 70 80 30
43 28 63 14 77 58 34 92 19 53 68 24
70 70 70 70 70 70 70 70 70 70 70 70
41 24 59 11 76 56 29 91 16 51 66 23
120 130 140 150 160 170 180 190 200 210 220 230
5 200 5 200 5 200 5 200 5 200 5 200
44 29 64 13 79 59 36 94 21 54 69 26

Sample Output 4

955

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

0