B - 観光地選び 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は旅行の計画を立てています。旅行先の候補として N 箇所の観光地があり、そのうち 0 箇所以上 K 箇所以下を選んで訪れることができます。ただし、同じ観光地を複数回選ぶことはできません。

各観光地 i（ i = 1, 2, \ldots, N ）にはお土産屋があり、 C_i 個のお土産が売られています。観光地 i の j 番目（ j = 1, 2, \ldots, C_i ）のお土産には満足度 V_{i,j} が定められています。満足度は負の値をとることもあります。

各観光地 i には評価値が定められています。評価値は、その観光地で売られている C_i 個のお土産の満足度の中央値です。ここで、中央値とは、 C_i 個の満足度を昇順に並べたときの \frac{C_i + 1}{2} 番目の値を指します。 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}
  • 1 行目には、観光地の数を表す整数 N と、訪れることができる最大箇所数を表す整数 K が、スペース区切りで与えられる。
  • 続いて、各観光地 i （ i = 1, 2, \ldots, N ）について 2 行ずつ与えられる。
  • 1 行目には、観光地 i のお土産の個数を表す奇数 C_i が与えられる。
  • 2 行目には、観光地 i の各お土産の満足度を表す整数 V_{i,1}, V_{i,2}, \ldots, V_{i,C_i} がスペース区切りで与えられる。

出力

訪れる観光地を 0 箇所以上 K 箇所以下選んだときの、選んだ観光地の評価値の合計の最大値を 1 行に出力せよ。

入力例 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

Score : 300 pts

Problem Statement

Takahashi is planning a trip. There are N candidate tourist spots, and he can choose to visit between 0 and K of them (inclusive). However, he cannot choose the same tourist spot more than once.

Each tourist spot i (i = 1, 2, \ldots, N) has a souvenir shop that sells C_i souvenirs. The j-th souvenir (j = 1, 2, \ldots, C_i) at tourist spot i has a satisfaction value V_{i,j}. Satisfaction values can be negative.

Each tourist spot i has a rating. The rating is the median of the satisfaction values of the C_i souvenirs sold at that tourist spot. Here, the median refers to the \frac{C_i + 1}{2}-th value when the C_i satisfaction values are sorted in ascending order. Since C_i is always odd, the median is uniquely determined and is an integer. Note that the rating can be negative.

Takahashi wants to maximize the sum of the ratings of the tourist spots he visits by choosing them wisely. If he visits no tourist spots, the sum of ratings is 0.

On behalf of Takahashi, find the maximum possible sum of ratings.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K \leq N
  • 1 \leq C_i \leq 99
  • C_i is odd
  • -1000 \leq V_{i,j} \leq 1000
  • All input values are integers

Input

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}
  • The first line contains an integer N representing the number of tourist spots and an integer K representing the maximum number of spots that can be visited, separated by a space.
  • Then, for each tourist spot i (i = 1, 2, \ldots, N), two lines are given:
  • The first line contains an odd number C_i representing the number of souvenirs at tourist spot i.
  • The second line contains integers V_{i,1}, V_{i,2}, \ldots, V_{i,C_i} representing the satisfaction values of each souvenir at tourist spot i, separated by spaces.

Output

Output in one line the maximum possible sum of ratings when choosing between 0 and K tourist spots (inclusive) to visit.

Sample Input 1

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

Sample Output 1

7

Sample Input 2

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

Sample Output 2

0

Sample Input 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

Sample Output 3

48

Sample Input 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

Sample Output 4

1666

Sample Input 5

1 1
1
-5

Sample Output 5

0