Problem Description

As an MMORPG enthusiast, Steve is thrilled to learn about the release of "World of Warcraft: Classic." He started playing from the first day of its release and is now just two levels away from reaching the maximum level. However, he doesn't have as much free time as he did when he first started, so he wants to level up as quickly as possible.

To level up the first time, Steve needs $s_1$ experience points. Only after gaining this amount of experience can he level up to the next level, which then requires $s_2$ experience points.

Steve has a list of $n$ tasks that he hopes to complete to reach the maximum level. It takes him $t_i$ minutes to complete the $i$-th task, which gives him $x_i$ experience points.

When Steve completes a task and has enough experience to level up, any excess experience beyond what is needed for the current level will be carried over to the next level. After leveling up, the experience gained from the $i$-th task will decrease to $y_i$, and the time required to complete the task will decrease to $r_i$.

It is important to note that once Steve completes a task, he cannot repeat it, regardless of whether he levels up or not.

Given the information about the tasks in the list, help Steve find an order to complete the tasks that minimizes the time required for him to reach the maximum level.

Input Format

The first line contains three integers $n, s_1, s_2 \ (1 \leq n, s_1, s_2 \leq 500)$, representing the number of tasks, the experience required to level up the first time, and the experience required to level up the second time.

The next $n$ lines each contain four integers $x_i, t_i, y_i, r_i \ (1 \leq y_i < x_i \leq 500, 1 \leq r_i < t_i \leq 10^9)$, representing the experience gained from the $i$-th task, the time required to complete it, the experience gained after leveling up, and the time required to complete it after leveling up.

Output Format

Output a single integer, representing the minimum number of minutes required for Steve to reach the maximum level. If it is impossible for him to reach the maximum level, output $-1$.

Sample Input and Output

Sample Input #1

2 100 100
100 100 10 10
101 11 100 10

Sample Output #1

110

Sample Input #2

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

Sample Output #2

40

Sample Input #3

2 20 5
10 10 5 5
10 10 5 5

Sample Output #3

-1

见题面 Input 部分

见题面 Output 部分