P12718 [Algo Beat Contest 002 E] Excellent Game

| Problem | Score | Idea | Std | Data | Check | Solution | | :----------------------------------: | :---: | :---------------------------------------------------: | :---------------------------------------------------: | :---------------------------------------------: | :-------------------------------------------------: | :----------------------------------------------------------: | | $\text{E - Excellent Game}$ | $500$ | [AFO_orchardist](https://www.luogu.com.cn/user/347582) | [AFO_orchardist](https://www.luogu.com.cn/user/347582) | [AFO_orchardist](https://www.luogu.com.cn/user/347582) | [LostKeyToReach](https://www.luogu.com.cn/user/764666) | [Link](https://www.luogu.com.cn/article/b8m53vtc) by [AFO_orchardist](https://www.luogu.com.cn/user/347582) | 戴戴刘传。

小 E 在玩一个极妙的数组游戏。游戏中共有 $N$ 个数组，每个数组长度为 $L_i$，元素分别为 $\{A_{i,1},A_{i,2},A_{i,3},\dots,A_{i,L_i}\}$。 游戏共有 $Q$ 轮，每轮需**恰好**进行一次操作。定义一次操作为，将某一个数组中的所有数增加 $K$。这里，$K$ 可能是负数。 小 E 想在游戏结束后，所有数组合起来 $\sum_{i=1}^n L_i$ 个元素中前 $M$ 大的元素之和尽可能大。小 E 不会玩这个游戏，所以让聪明的你来帮他求出这个最大值。 **前 $M$ 大的数**表示将这些数从大到小排序后的前 $M$ 位。

第一行输入四个整数 $N,M,Q,K$，含义见题目描述。 接下来，对于满足 $1 \le i \le N$ 的每一个 $i$，第 $2i$ 行输入一个整数 $L_i$，第 $2i+1$ 行输入 $L_i$ 个整数，描述第 $i$ 个数组。

输出一行一个整数，表示答案。

**【样例解释 #1】** 以下是一种可行的最优策略： 第一次操作在第 $3$ 个数组上，第二次操作在第 $4$ 个数组上，这样最大的 $4$ 个数之和为 $12+11+10+9=42$。 可以证明，没有比此更优的策略，使得答案大于 $42$。 **【数据范围】** - $1 \le N,Q \le 2 \times 10^5$。 - $1 \le M \le \sum_{i=1}^n L_i \le 2 \times 10^5$。 - $-10^7 \le K \le 10^7$。 - $-10^{12} \le A_{i,j} \le 10^{12}$。