モールを訪れたときに、そのモールの中で買い物をする店舗は自由に（これまでに訪れたモールや店舗、これから訪れるモールや店舗とは関係なく）選ぶことができます。 また、店舗のお得度がすべて正なので、モールを訪れたらそのモールの中にある店舗すべてで買い物をするべきです。

以上の考察から、それぞれのモールに対して「そのモールを訪問したときに得られる最大の利得」を求めることができます。 この値を使うと、この問題は次のような問題に言い換えることができます。

\(i\) 番目 \((1\le i\le N)\) のモールを訪れると \(B _ i\) の利得が得られる。 モールを \(K\) 個まで重複せずに選び（\(0\) 個でもよい）、利得の合計を最大化せよ。

これは、利得が大きいほうからモールを \(K\) 個見て、\(B _ i\ge0\) ならそのモールを訪れることで解くことができます。 証明は省略しますが、最適なモールの訪れ方とこのアルゴリズムで得られる訪れ方が異なるときの訪れるモールの差（一方で訪れてもう一方で訪れないモール）について考えると示すことができます。

利得が大きいほうからモールを \(K\) 個見る操作を実現する方法は、例えば以下のようなものがあります。

• 利得の列をソートし、大きいほうから順に \(K\) 個見る。時間計算量は \(O(\sum _ {i=1} ^ N M _ i+N\log N)\) 、空間計算量は \(O(N)\) などになります。
• 優先度付きキューなどを使い、利得を計算しながら上位 \(K\) 個だけを保持して更新する。時間計算量は \(O(\sum _ {i=1} ^ N M _ i+N\log K)\) 、空間計算量は \(O(K)\) などになります。
• 選択アルゴリズムなどを利用し、利得の列の上位 \(K\) 個を求める。時間計算量は \(O(\sum _ {i=1} ^ N M _ i+N)\) 、空間計算量は \(O(N)\) などになります。

いずれの方針でもこの問題は十分高速に解くことができます。

実装例は以下のようになります。 \(B _ i\) を \(-C _ i+\displaystyle\sum _ {j=1} ^ {K _ i}P _ {i,j}\) ではなく \(\max\!\left\lbrace0,-C _ i+\displaystyle\sum _ {j=1} ^ {K _ i}P _ {i,j}\right\rbrace\) と定義すると、「\(B _ i\ge0\) ならそのモールを訪れる」の分岐が不要になります。 C++ などの言語を用いて解いている場合、\(B _ i\) の値が符号付き \(32\operatorname{bit}\) 整数型に収まらない場合があることに注意してください。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;

    vector<long> benefit(N); // benefit[i] := i 番目のモールから得られる利得の最大値
    for (long& b : benefit) {
        int C;
        cin >> C;
        b -= C; // 訪問費用を引き

        int K;
        cin >> K;
        for (int i = 0; i < K; ++i) {
            int P;
            cin >> P;
            b += P; // それぞれのお店のお得度を足す
        }

        b = max(0L, b); // 利得が負だったら訪れない
    }

    ranges::nth_element(benefit, begin(benefit) + K, greater{}); // 利得の大きいほうから K 個を求める

    long ans = 0;
    for (int i = 0; i < K; ++i) { // 先頭から K 個の合計を求める
        ans += benefit[i];
    }
    cout << ans << endl; // 答えを出力する

    // #include <ranges>
    // としておいて、
    // cout << ranges::fold_left(benefit | views::take(K), 0L, plus{}) << endl;
    // としても先頭 K 個の合計を出力できます。

    return 0;
}

N, K = map(int, input().split())

B = [] # モールから得られる利得の最大値を入れるリスト

for _ in range(N):
    C, M, *P = map(int, input().split())
    # モール内のすべてのお店を訪れたときの利得と、0 との最大値を求める
    B.append(max(0, sum(P) - C))

print(sum(sorted(B)[-K:])) # ソートして大きいほう K 個の合計が答え