← 返回题目列表

AtCoder · awc0021_c

C. 特价购物中心之旅

中文机器翻译题面 查看原题

分数: 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