P5798 [SEERC 2019] Level Up

As an MMORPG fan, Steve was very excited to hear that *World of Warcraft: Classic* was released. He started playing on the first day of release, and now he is only $2$ levels away from reaching the maximum level. Of course, he does not have as much free time as when he first started, so he wants to reach the maximum level as quickly as possible. To gain the first level, he needs $s_1$ experience points. Only after he has obtained that much experience can he level up, and the second level then requires another $s_2$ experience points to level up. Steve has a quest list with $n$ quests. He wants to reach the maximum level by completing some of these quests. Steve needs $t_i$ minutes to complete quest $i$, and this quest gives him $x_i$ experience points. When Steve completes a quest and can level up, any experience beyond what is required to level up will carry over to the next level. After he levels up once, the experience gained from quest $i$ decreases to $y_i$, and the time needed to complete it also decreases to $r_i$. Note that quests Steve has completed **cannot** be taken again, regardless of whether he has leveled up. Given the information of the quests in the list, help Steve find an order of completing quests such that the total time needed to reach the maximum level is minimized.

The first line contains three integers $n, s_1, s_2 \ (1 \leq n, s_1, s_2 \leq 500)$, representing the number of quests, the experience required to gain the first level, and the experience required to gain the second level. 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 quest $i$, the time needed to complete it, the experience gained after leveling up once, and the time needed after leveling up once.

Output one integer, the minimum number of minutes Steve needs to reach the maximum level. If it is impossible to reach the maximum level no matter what, output $-1$.

Translated by ChatGPT 5