Demon King's Shield Breaker

In the Demon King's castle, the protective shield has a health value of $x$. Small A wants to destroy the shield within $n$ days. At the beginning of each day, small B's magic power is restored to $m$, but his magic power cannot exceed a maximum value $M$. When small B uses his burst magic (which can be used only once per day), every unit of his current magic power deals one point of damage to the shield. That is, if his magic power at that moment is $p$, then the damage dealt is $p$.

To ensure that enough damage is done, small A is allowed to purchase magic crystals from the shop on each day, which can boost small B's magic power. However, the shop sells a different number of magic crystals every day and each crystal has its own magic power bonus and price. Note: Magic crystals bought on a day must be used on that day; they expire at the end of the day. Also, if a crystal’s magic power bonus $h$ added to small B's current magic power $m$ would exceed $M$, then his magic power becomes $M$. In other words, if you add a crystal with bonus $h$, his updated magic power is given by [ m' = \min(M, m+h). ]

Determine the minimum amount of money small A needs to spend so that over the course of $n$ days, the total damage (i.e. the sum of the magic power available on each day after purchasing crystals) is at least $x$. If it is impossible to reach or exceed $x$, output -1.

Input Format: The first line contains four integers $x$, $n$, $m$, and $M$. Each of the next $n$ blocks describes one day. For each day, the first line contains an integer $k$ representing the number of magic crystals available that day. Then follow $k$ lines; each line contains two integers $h$ and $p$, where $h$ is the magic power bonus provided by that crystal and $p$ is its price.

Note: Without buying any crystals, small B’s damage on each day is $m$, so the damage boost that can be achieved on any day is at most $M-m$. You may purchase a subset of the available crystals each day (each crystal can be used at most once) to raise his magic power from $m$ to at most $M$, thus increasing that day’s damage by at most $M-m$.

inputFormat

The input begins with a line containing four integers: $x$, $n$, $m$, and $M$, where $x$ is the required total damage, $n$ is the number of days, $m$ is the base magic power per day, and $M$ is the maximum magic power per day. Then, for each day, there is a block of input beginning with an integer $k$ (the number of magic crystals available that day). This is followed by $k$ lines, each containing two integers $h$ and $p$, which denote the magic power bonus and the price of that crystal, respectively.

outputFormat

Output a single integer representing the minimum total cost required to achieve at least $x$ damage over $n$ days. If it is impossible, output -1.

sample

20 3 5 10
2
3 4
5 10
1
2 3
2
4 7
1 2

10