← 返回题目列表

AtCoder · awc0091_b

B. 选择旅游景点

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

分数: 300 分

问题陈述

高桥正在计划旅行。有 N 候选旅游点,他可以选择游览 其中 0 和 K (含)。然而,他不能多次选择同一个旅游景点。

各旅游点 i (i = 1, 2, \ldots, N)有一家纪念品商店,出售 C_i 纪念品。的 j第纪念品(j = 1, 2, \ldots, C_i) 在旅游景点 i 有满意度值 V_{i,j}。满意度值可能为负值。

各旅游点 i 有一个 评级。评级是 中位数 长度为 $$$n$$$ 的数组 $$$a$$$ 的 的满意度值 C_i 那个旅游景点出售的纪念品。这里,中位数指的是 \frac{C_i + 1}{2}-第一个值,当 C_i 满意度值按升序排序。自从 C_i 始终为奇数,中位数唯一确定并且是整数。请注意,评级可能为负。

高桥希望通过明智地选择他所访问的旅游景点来最大化其评分总和。如果他没有访问任何旅游景点,则评分总和为 0.

代表高桥,找出最大可能的评分总和。

约束

  • 1 \leq N \leq 100
  • 1 \leq K \leq N
  • 1 \leq C_i \leq 99
  • C_i 是奇数
  • -1000 \leq V_{i,j} \leq 1000
  • 所有输入值均为整数

输入

N K
C_1
V_{1,1} V_{1,2} \ldots V_{1,C_1}
C_2
V_{2,1} V_{2,2} \ldots V_{2,C_2}
\vdots
C_N
V_{N,1} V_{N,2} \ldots V_{N,C_N}
  • 第一行包含一个整数 N 代表旅游点的数量和一个整数 K 代表可以访问的最大景点数,以空格分隔。
  • 然后,对于每个旅游景点 i (i = 1, 2, \ldots, N),给出两行:
  • 第一行包含奇数 C_i 代表旅游景点的纪念品数量 i.
  • 第二行包含整数 V_{i,1}, V_{i,2}, \ldots, V_{i,C_i} 代表旅游景点每种纪念品的满意度值 i,以空格分隔。

输出

在一行中输出选择时的最大可能评级总和 0 和 K 旅游点(含)参观。


示例输入 1

3 2
3
3 1 2
3
5 -1 10
3
-3 -5 -1

示例输出 1

7

示例输入 2

3 2
3
-5 -3 -7
3
-10 -1 -4
3
-2 -8 -6

示例输出 2

0

示例输入 3

5 3
5
10 20 30 5 15
3
-2 3 1
7
100 -50 0 25 75 50 -10
3
-1 -2 -3
3
7 8 9

示例输出 3

48

示例输入 4

10 5
5
12 -3 7 20 -8
3
100 200 150
7
-5 -10 3 8 -1 0 6
1
-1000
9
50 40 30 20 10 0 -10 -20 -30
3
999 998 1000
5
-100 -200 -300 -400 -500
1
500
3
0 0 0
5
1 2 3 4 5

示例输出 4

1666

示例输入 5

1 1
1
-5

示例输出 5

0