Overview

First, compute the “evaluation value (median of souvenir satisfaction)” for each tourist spot, then select up to \(K\) spots (only those with positive evaluation values) starting from the highest evaluation value to maximize the total evaluation value.

Analysis

Key Insight

• Regardless of which tourist spots are selected, the evaluation value of each individual spot does not change (there is no interaction between spots).
• Therefore, the problem can be rephrased as: “Given \(N\) numbers (the evaluation value of each tourist spot), select between \(0\) and \(K\) of them to maximize the total sum.”

The optimal strategy is then obvious: - Select spots in decreasing order of evaluation value. - Since selecting \(0\) spots is allowed, there is no benefit to selecting a negative evaluation value (it only decreases the total).

In other words, the optimal approach is “sort the evaluation values in descending order, and sum up to \(K\) values from the top, but only the positive ones.”

Why a Naive Approach Fails

Exhaustively searching all subsets of tourist spots yields \(2^N\) possibilities. Since \(N \le 100\), \(2^{100}\) is far too large to handle.

This problem can be solved simply by “computing the evaluation value of each tourist spot, then greedily taking the largest ones.”

Concrete Example

For example, if the evaluation values are \([5, 3, -1, 2]\) and \(K=2\): - Sort in descending order: \([5, 3, 2, -1]\) - Sum up to 2 positive values from the top: \(5+3=8\) (Since we don’t have to select exactly \(K\) spots, we exclude negative values)

Algorithm

1. For each tourist spot \(i\):
   1. Sort the souvenir satisfaction values \(V_{i,1}, \dots, V_{i,C_i}\) in ascending order.
   2. Since \(C_i\) is odd, the median is the value at \(0\)-indexed position \(C_i//2\) (corresponding to the \(\frac{C_i+1}{2}\)-th element).
   3. Store this median as the “evaluation value” in the array medians.
2. Sort medians in descending order.
3. Iterate through up to \(K\) values from the top, summing only while they are positive (once a value \(\le 0\) appears, all subsequent values are also \(\le 0\), so we can stop).
4. Output the total sum (if no spot is selected, the result is naturally \(0\)).

Complexity

• Time complexity: Sorting for each tourist spot takes \(O(C_i \log C_i)\), and sorting the evaluation value array takes \(O(N \log N)\), so the overall complexity is \(O\!\left(\sum_{i=1}^{N} C_i \log C_i + N \log N\right)\) (Since \(C_i \le 99\) under the constraints, this is sufficiently fast.)
• Space complexity: \(O(\max C_i + N)\) (arrays for each tourist spot and the median array)

Implementation Notes

• The median can be obtained as vals[C//2] after sorting in ascending order (since \(C\) is odd, it is unique).

• Since selecting \(0\) spots is allowed, it is optimal not to select any spot with evaluation value \(\le 0\). After sorting in descending order, we can stop as soon as a value \(\le 0\) appears.

• Since the input can be quite long, using sys.stdin.read() to read everything at once makes the implementation concise and fast.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    it = iter(data)
    N = next(it)
    K = next(it)

    medians = []
    for _ in range(N):
        C = next(it)
        vals = [next(it) for _ in range(C)]
        vals.sort()
        medians.append(vals[C // 2])

    medians.sort(reverse=True)
    ans = 0
    for i in range(min(K, N)):
        if medians[i] <= 0:
            break
        ans += medians[i]
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.