题目背景

小 A 目前正在带着小 B 进行攻打魔王城的每日一爆演练。

题目描述

具体来说，魔王城的结界护盾共有 $x$ 的血量，小A想在 $n$ 天内完成对魔王城护盾的破坏。每天小 B 的魔力值会恢复至 $m$ ，且魔力值的上限为 $M$ ，使用爆裂魔法时每 $1$ 点魔力值可以对魔王城护盾造成 $1$ 点伤害。当然，爆裂魔法每天只能使用一次。

为了确保小 B 可以造成充足的伤害，小 A 每天可以花钱去商店购买魔晶石为小 B 增加魔力值。但是商店每天出售的魔晶石的数量、价格、和魔力值都有所不同。且当天出售的魔晶石只能当天使用，不然会过期，无法补充魔力。小A现在想知道，如果要小 B 能够顺利爆破魔王城的护盾，最少需要花费多少钱？（如果无法完成破坏，则输出 -1）

注意：由于小 B 的魔力值具有上限，因此当魔晶石魔力含量 $h$ 加上小 B 当前魔力值 $m$ 大于等于 $M$ 时，使用该魔晶石只能使小 B 的魔力值变为 $M$ ，也就是说 $m'=\min(M,m+h)$ 。

输入格式

第一行输入四个正整数，$n,x,M,m$ （$1 \le n,x,M \le 5000,m \le M$）。

接下来会有 $n$ 组数据，每组数据有三行。

第一行代表第 $i$ 天出售的魔晶石数量 $\text{num}_i\ (1 \le \text{num} \le 5000)$ ，数据保证 $\sum_{i=1}^{n}\text{num}_i\le 5000$。

第二行共 $\text{num}_i$ 个正整数，代表第 $i$ 天出售的第 $j$ 个魔晶石的价格 $p_{i,j}\ (1\le p_{i,j} \le 10^9)$ 。

第三行共 $\text{num}_i$ 个正整数，代表第 $i$ 天出售的第 $j$ 个魔晶石的魔力值 $h_{i,j}\ (1 \le h_{i,j} \le M)$ ，数据保证 $\sum_{i=1}^{n}\sum_{j=1}^{\text{num}_i}h_{i,j}\le 5000$。

输出格式

输出一个整数，代表所求的答案。

2 17 10 6
3
1 1 2
2 1 7
2
1 2
3 4

2

2 20 10 8
3
10 2 3
8 2 1
1
1
1

-1

2 17 10 9
3
1 1 2
2 2 7
2
1 2
3 4

0

提示

样例解释：

样例 1 中，可以选择购买第一天的第一个魔晶石，花费为 $1$，当天总魔力值为 $8$。再购买第二天的第一个魔晶石，花费为 $1$，当天总魔力值为 $9$。这样两天总共可以造成 $17$ 点伤害，成功破坏结界，且花费最少为 $2$。

样例 2 中，因为存在魔力值上限，因此第一天最多造成 $10$ 点伤害，而第二天最多造成 $9$ 点伤害，因此无法破坏结界。