Level Up

Time limit2sMemory limit256 MB

Summary

Given quests that give experience and cost time on two levels, find the minimum total time to clear both levels, with overflow carrying over, or -1 if impossible.

Level: Medium6 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Being a fan of MMORPGs, Steve was really excited when World of Warcraft Classic was announced. He started playing from the first day and now has only two levels to go till the maximum level. Of course, he doesn't have as much time as he used to have when the game first appeared, so he really wants to finish these two levels as fast as possible.

In order to pass the first level, Steve needs $s_1$ experience. Only after he gains it, he can move to the second level, in which he needs to get other $s_2$ experience to pass it.

Steve has a list of $n$ available quests. He knows that he may finish two levels with these quests. To pass the $i$ -th quest, Steve needs $t_i$ minutes. As a result, he will get $x_i$ experience for this quest.

When Steve finishes a quest that takes him to the next level, the extra experience overflow is subtracted from the next level's required experience. Once he levels up, all the quests that are left will offer less experience $y_i$ , but they will also require less time $r_i$ .

Note that if Steve finishes a quest, he cannot repeat this quest anymore (even in another level).

Given the list of quests, help Steve choose the order in which he will do the quests so that he finishes the last two levels as fast as possible.

Input

The first line contains three integers $n$ , $s_1$ , $s_2$ ( $1 \le n, s_1, s_2 \le 500$ ), the number of quests, the experience required for the first level, and the experience required for the second level.

Each of the next $n$ lines contains four integers $x_i$ , $t_i$ , $y_i$ , $r_i$ ( $1 \le y_i < x_i \le 500$ , $1 \le r_i < t_i \le 10^9$ ), where $x_i$ and $y_i$ are the experience you gain from the $i$ -th quest on the first and second level, and $t_i$ and $r_i$ are the minutes you need to pass this quest on the first and second level.

Output

Print one number, the minimum number of minutes Steve needs to finish both levels, or $-1$ if there is no way to complete the quests to finish both levels.

Examples3

Example 1

Input

2 100 100
100 100 10 10
101 11 100 10

Expected output

Example 2

Input

4 20 20
40 1000 20 20
6 6 5 5
10 10 1 1
10 10 1 1

Expected output

Example 3
Input
```
2 20 5
10 10 5 5
10 10 5 5
```
Expected output
```
-1
```