分数: 333 分
问题陈述
高桥正计划访问 N 郊区商场购物期间有周末特卖。
各商场 i (1 \leq i \leq N)有 M_i 商店,各卖特卖商品。如果高桥在 j第商店( 购物中心的1 \leq j \leq M_i) i,他可获得的收益值为 P_{i,j} 日元。
参观购物中心 i,他必须支付以下费用 C_i 日元。该成本是为每个购物中心确定的固定值。
由于时间有限,高桥最多只能选择参观 K 商场出 N 购物中心(也可以不参观)。他不能多次访问同一个商场。
在他访问的每个购物中心,他可以从以下位置选择任意数量(零个或更多)的商店 M_i 该商场内的商店可供购物。他最多可以在每家商店购物一次。请注意,即使他没有选择所参观的商场中的任何商店,他仍然必须支付参观费用 C_i.
最大化 利润总额 高桥可以获得的 。利润总额定义如下:
\text{Total profit} = \sum_{\text{stores } (i,j) \text{ where he shopped}} P_{i,j} - \sum_{\text{malls } i \text{ he visited}} C_i
也就是说,是他逛过的所有商店的效益值之和,减去他去过的所有商场的参观成本之和。如果他不逛商场,总利润是 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}
- 第一行包含商场数量 N 以及可访问的最大商场数量 K,用空格分隔。
- 在下面 N 行, i- 第行 (1 \leq i \leq N) 包含参观费用 商场的 C_i 商场的 i, 商店数量 M_i,以及效益值 每个商店的 P_{i,1}, P_{i,2}, \ldots, P_{i,M_i} ,以空格分隔(包括 2 + M_i 值)。
输出
在一行中打印高桥可以获得的最大总利润。
示例输入 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