C. Trail Running
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a trail race, there is no shame in walking for part of the race! Walking up a steep hill can save energy and allow a runner to achieve a better overall time.

You are running a trail race this weekend, and you know that your body can expend a total of $$$E$$$ units of energy before you'll be too exhausted to finish the race. For each mile of the race, you can choose to either walk or run. Each strategy consumes a certain amount of energy and takes a certain amount of time.

Compute the fastest you can finish the race.

Input

The first line of input contains two space-separated integers $$$N$$$ $$$(1 \leq N \leq 50)$$$ and $$$E$$$ $$$(1 \leq E \leq 1\,000)$$$, the number of miles in the race and the maximum energy you can consume, respectively.

Each of the next $$$N$$$ lines contains four space-separated integers $$$e_1$$$, $$$t_1$$$, $$$e_2$$$, and $$$t_2$$$ $$$(0 \leq e_1, e_2 \leq 1\,000; 1 \leq t_1, t_2 \leq 10\,000)$$$: the amount of energy it costs to walk the mile, how many seconds doing so takes, the amount of energy it costs to run the mile instead, and how many seconds running the mile takes.

Note that it is not necessarily the case that $$$e_1 \lt e_2$$$ or $$$t_1 \gt t_2$$$.

Output

Print a single integer: the fastest time (in seconds) you can complete the race. If it is impossible to finish the race no matter the strategy, print $$$-1$$$ instead.

Examples
Input
3 100
1 600 50 450
1 650 50 400
1 500 50 500
Output
1500
Input
3 100
40 125 35 100
35 200 35 180
50 500 31 430
Output
-1
Note

In the first sample, Magikarp can walk the first and third miles and run the second. This uses $$$52$$$ energy and takes $$$600+400+500=1500$$$ seconds, which is the minimum time possible.

In the second sample, even the least-energy choice on each mile uses $$$35+35+31=101$$$ energy, more than the limit of $$$100$$$. Therefore finishing is impossible.