/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は週末のセールで買い物をするため、郊外にある N 個のショッピングモールを巡ることを計画しています。
各ショッピングモール i（1 \leq i \leq N）には M_i 個の店舗があり、それぞれの店舗ではセール品が販売されています。ショッピングモール i の j 番目の店舗（1 \leq j \leq M_i）で買い物をすると、P_{i,j} 円のお得度を得ることができます。
ショッピングモール i を訪れるには、訪問費用として C_i 円を支払う必要があります。この費用はモールごとに決まった固定の値です。
高橋君は時間の都合上、N 個のモールの中から K 個以下のモールを選んで訪れることができます（1 つも訪れないことも可能です）。同じモールを複数回訪れることはできません。
訪れたモールでは、そのモールにある M_i 個の店舗の中から好きな店舗を 0 個以上選んで買い物をすることができます。同じ店舗で買い物をできるのは 1 回までです。なお、訪れたモールで 1 つも店舗を選ばなかった場合でも、訪問費用 C_i は支払う必要があります。
高橋君が得られる 合計利得 を最大化してください。合計利得は次のように定義されます。
\text{合計利得} = \sum_{\text{買い物をした店舗 } (i,j)} P_{i,j} - \sum_{\text{訪れたモール } i} C_i
すなわち、買い物をした全店舗のお得度の総和から、訪れた全モールの訪問費用の総和を引いた値です。1 つもモールを訪れない場合、合計利得は 0 です。したがって、合計利得の最大値は 0 以上になります。
制約
- 1 \leq N \leq 10^5
- 1 \leq K \leq N
- 1 \leq M_i \leq 100
- \sum_{i=1}^{N} M_i \leq 10^5
- 1 \leq C_i \leq 10^9
- 1 \leq P_{i,j} \leq 10^9
- 入力はすべて整数である
入力
N K
C_1 M_1 P_{1,1} P_{1,2} \ldots P_{1,M_1}
C_2 M_2 P_{2,1} P_{2,2} \ldots P_{2,M_2}
\vdots
C_N M_N P_{N,1} P_{N,2} \ldots P_{N,M_N}
- 1 行目には、ショッピングモールの数 N と、訪れることができるモールの最大数 K が、スペース区切りで与えられる。
- 続く N 行のうち i 行目（1 \leq i \leq N）には、モール i の訪問費用 C_i、店舗の数 M_i、および各店舗のお得度 P_{i,1}, P_{i,2}, \ldots, P_{i,M_i} が、スペース区切りで与えられる（2 + M_i 個の値からなる）。
出力
高橋君が得られる合計利得の最大値を 1 行で出力せよ。
入力例 1
3 2 500 3 200 300 100 300 2 400 150 800 4 250 250 250 250
出力例 1
450
入力例 2
4 3 100 2 50 60 200 3 300 100 50 150 1 100 80 2 90 85
出力例 2
355
入力例 3
5 2 1000000000 5 500000000 400000000 300000000 200000000 100000000 100 3 50 40 30 999999999 2 1000000000 1000000000 500 4 200 150 100 80 10000 10 5000 4000 3000 2000 1000 900 800 700 600 500
出力例 3
1500000001
Score : 333 pts
Problem Statement
Takahashi is planning to visit N shopping malls in the suburbs to shop during a weekend sale.
Each shopping mall i (1 \leq i \leq N) has M_i stores, each selling sale items. If Takahashi shops at the j-th store (1 \leq j \leq M_i) of shopping mall i, he can gain a benefit value of P_{i,j} yen.
To visit shopping mall i, he must pay a visiting cost of C_i yen. This cost is a fixed value determined for each mall.
Due to time constraints, Takahashi can choose and visit at most K malls out of the N malls (it is also possible to visit none). He cannot visit the same mall more than once.
At each mall he visits, he can choose any number (zero or more) of stores from the M_i stores in that mall to shop at. He can shop at each store at most once. Note that even if he does not choose any store at a mall he visits, he still must pay the visiting cost C_i.
Maximize the total profit that Takahashi can obtain. The total profit is defined as follows:
\text{Total profit} = \sum_{\text{stores } (i,j) \text{ where he shopped}} P_{i,j} - \sum_{\text{malls } i \text{ he visited}} C_i
In other words, it is the sum of benefit values of all stores where he shopped, minus the sum of visiting costs of all malls he visited. If he visits no malls, the total profit is 0. Therefore, the maximum total profit is at least 0.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq K \leq N
- 1 \leq M_i \leq 100
- \sum_{i=1}^{N} M_i \leq 10^5
- 1 \leq C_i \leq 10^9
- 1 \leq P_{i,j} \leq 10^9
- All input values are integers
Input
N K
C_1 M_1 P_{1,1} P_{1,2} \ldots P_{1,M_1}
C_2 M_2 P_{2,1} P_{2,2} \ldots P_{2,M_2}
\vdots
C_N M_N P_{N,1} P_{N,2} \ldots P_{N,M_N}
- The first line contains the number of shopping malls N and the maximum number of malls that can be visited K, separated by a space.
- In the following N lines, the i-th line (1 \leq i \leq N) contains the visiting cost C_i of mall i, the number of stores M_i, and the benefit values P_{i,1}, P_{i,2}, \ldots, P_{i,M_i} of each store, separated by spaces (consisting of 2 + M_i values).
Output
Print the maximum total profit that Takahashi can obtain, in a single line.
Sample Input 1
3 2 500 3 200 300 100 300 2 400 150 800 4 250 250 250 250
Sample Output 1
450
Sample Input 2
4 3 100 2 50 60 200 3 300 100 50 150 1 100 80 2 90 85
Sample Output 2
355
Sample Input 3
5 2 1000000000 5 500000000 400000000 300000000 200000000 100000000 100 3 50 40 30 999999999 2 1000000000 1000000000 500 4 200 150 100 80 10000 10 5000 4000 3000 2000 1000 900 800 700 600 500
Sample Output 3
1500000001