题目背景

PPX 终于考上了大学，为了激励自己好好学习，他设立了一个奖学金。奖学金发放规则是：全班 $n$ 个同学按期末总成绩从高到低排名，PPX 想给前 $k$ 名的同学每人发放 $x$ 元奖金。

但是 PPX 的智商有限，算不清楚到底应该发多少钱，于是他决定找到一个合适的 $x$。

题目描述

全班有 $n$ 个同学，第 $i$ 个同学有 $a_i$ 门课程的成绩，每门课满分是 $100$ 分。每个同学的总成绩是这 $a_i$ 门课成绩的平均值（可以不是整数）。

PPX 事先设定了一个奖金总额 $M$，他想给前 $k$ 名的同学每人发 $x$ 元奖金，要求：

1. 前 $k$ 名同学每人拿到的奖金都是 $x$ 元。
2. 第 $k$ 名和第 $k+1$ 名的总成绩差距至少为 $t$ 分（即第 $k$ 名的总成绩 - 第 $k+1$ 名的总成绩 $\ge t$），这样才显得公平。
3. 总奖金 $k \times x$ 不能超过预算 $M$。

现在 PPX 想知道，在满足上述条件的情况下，$x$ 最大可以是多少。

如果无论如何都无法满足条件（即没有任何 $x$ 能使前 $k$ 名总成绩差距达到 $t$），输出 -1。

输入格式

第一行四个整数 $n, k, t, M$，分别表示人数、获奖人数、成绩差距要求、总预算。
接下来 $n$ 行，每行第一个整数 $a_i$ 表示第 $i$ 个同学的课程数量，后面 $a_i$ 个整数表示每门课的成绩。

输出格式

输出一个整数，表示最大的 $x$。如果不存在，输出 -1。

输入输出样例 #1

输入 #1

5 3 5 100
3 80 85 90
2 95 100
4 70 75 80 85
3 60 65 70
2 50 60

输出 #1

33

输入输出样例 #2

输入 #2

4 2 10 50
3 90 92 95
3 88 89 90
2 85 86
2 70 75

输出 #2

-1

说明/提示

说明/提示

数据范围

每个数据有 $30\%$ 的概率，满足 $1 \le n \le 100$，$1 \le a_i \le 5$，$1 \le M \le 10^4$。
每个数据有 $60\%$ 的概率，满足，$1 \le n \le 10^4$，$1 \le a_i \le 10$，$1 \le M \le 10^6$。
每个数据有 $100\%$ 的概率，满足，$1 \le n \le 10^5$，$1 \le a_i \le 100$，$1 \le M \le 10^9$，$1 \le k \le n$，$1 \le t \le 100$，每门课成绩 $0 \le score \le 100$。

样例解释

样例 1：

• 计算每个同学的平均分：
  • 同学1：$(80+85+90)/3 = 85$
  • 同学2：$(95+100)/2 = 97.5$
  • 同学3：$(70+75+80+85)/4 = 77.5$
  • 同学4：$(60+65+70)/3 = 65$
  • 同学5：$(50+60)/2 = 55$
• 排名：$97.5 > 85 > 77.5 > 65 > 55$
• 前 $3$ 名是同学2、同学1、同学3
• 第 $3$ 名（同学3）77.5分，第4名（同学4）65分，差距 12.5 $\ge 5$，满足。
• 预算 $M=100$，$k=3$，所以 $3x \le 100$，$x$ 最大为 $33$。