Problem Background

Little A is currently conducting daily explosion drills with Little B to conquer the Demon King's castle.

Problem Description

Specifically, the Demon King's castle has a shield with $x$ health points. Little A wants to destroy this shield within $n$ days. Each day, Little B's magic power resets to $m$, with an upper limit of $M$. Each point of magic power can inflict $1$ point of damage to the Demon King's shield. However, the explosion spell can only be used once per day.

To ensure Little B can inflict sufficient damage, Little A can buy magic crystals from the store to increase Little B's magic power. However, the quantity, price, and magic power of the crystals sold each day vary, and the crystals can only be used on the day they are purchased, otherwise, they will expire and cannot replenish magic power. Little A wants to know the minimum amount of money needed for Little B to successfully destroy the Demon King's shield. If it is not possible to destroy the shield, output -1.

Note: Since Little B's magic power has an upper limit, when the magic power content $h$ of a crystal plus Little B's current magic power $m$ is greater than or equal to $M$, using this crystal will only bring Little B's magic power to $M$, that is, $m'=\min(M,m+h)$.

Input Format

The first line contains four positive integers, $n, x, M, m$ ($1 \le n, x, M \le 5000, m \le M$).

The following will be $n$ sets of data, each set containing three lines.

The first line of each set represents the number of magic crystals sold on the $i$-th day, $\text{num}_i$ ($1 \le \text{num} \le 5000$), with the guarantee that $\sum_{i=1}^{n}\text{num}_i\le 5000$.

The second line contains $\text{num}_i$ positive integers, representing the price $p_{i,j}$ ($1 \le p_{i,j} \le 10^9$) of the $j$-th magic crystal sold on the $i$-th day.

The third line contains $\text{num}_i$ positive integers, representing the magic power $h_{i,j}$ ($1 \le h_{i,j} \le M$) of the $j$-th magic crystal sold on the $i$-th day, with the guarantee that $\sum_{i=1}^{n}\sum_{j=1}^{\text{num}_i}h_{i,j}\le 5000$.

Output Format

Output a single integer, representing the minimum amount of money required.

Sample Input and Output

Input Sample #1

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

Output Sample #1

2

Input Sample #2

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

Output Sample #2

-1

Input Sample #3

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

Output Sample #3

0

Notes

Sample Explanation:

In Sample 1, you can choose to buy the first magic crystal on the first day, costing $1$, with a total magic power of $8$ for that day. Then buy the first magic crystal on the second day, costing $1$, with a total magic power of $9$ for that day. This way, the total damage over the two days is $17$, successfully destroying the shield with the minimum cost of $2$.

In Sample 2, due to the magic power limit, the maximum damage on the first day is $10$, and the maximum damage on the second day is $9$, so it is impossible to destroy the shield.

见题面 Input 部分

见题面 Output 部分