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