Background

A is currently taking B to do a daily explosion training session for raiding the Demon King’s castle.

Problem Description

More specifically, the barrier shield of the Demon King’s castle has $x$ HP. A wants to finish destroying the shield within $n$ days. Every day, B’s mana will recover to $m$, and the mana cap is $M$. When using explosion magic, each $1$ point of mana can deal $1$ point of damage to the shield. Of course, explosion magic can only be used once per day.

To make sure B can deal enough damage, A can spend money every day to buy mana crystals from the shop to increase B’s mana. However, the number, price, and mana value of the mana crystals sold each day are different. Also, the mana crystals sold on that day can only be used on that day, otherwise they will expire and cannot restore mana. A now wants to know: if B is to successfully blow up the shield of the Demon King’s castle, what is the minimum amount of money needed? (If it is impossible to destroy it, output -1.)

Note: Since B’s mana has an upper limit, when a crystal with mana value $h$ plus B’s current mana $m$ is greater than or equal to $M$, using this crystal can only set B’s mana 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$).

Then there are $n$ groups of data, each group consisting of three lines.

The first line gives the number of mana crystals sold on day $i$, $\text{num}_i$ $(1 \le \text{num} \le 5000)$. The data guarantees $\sum_{i=1}^{n}\text{num}_i\le 5000$.

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

The third line contains $\text{num}_i$ positive integers, where the $j$-th integer is the mana value of the $j$-th mana crystal sold on day $i$, $h_{i,j}\ (1 \le h_{i,j} \le M)$. The data guarantees $\sum_{i=1}^{n}\sum_{j=1}^{\text{num}_i}h_{i,j}\le 5000$.

Output Format

Output one integer, which is the required answer.

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

Hint

Sample explanation:

In Sample 1, you can choose to buy the first mana crystal on day 1, costing $1$, making the total mana that day $8$. Then buy the first mana crystal on day 2, costing $1$, making the total mana that day $9$. In this way, the total damage over two days is $17$, successfully destroying the barrier, and the minimum cost is $2$.

In Sample 2, because there is a mana cap, at most $10$ damage can be dealt on day 1, and at most $9$ damage can be dealt on day 2, so the barrier cannot be destroyed.

Translated by ChatGPT 5