题目背景

戴戴刘传。

题目描述

小 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$ 个数组。

输出格式

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

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

42

4 4 2 -2
4
-1 2 -3 4
3
-5 6 -7
2
-8 9
1
100

115

提示

【样例解释 #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}$。