MMORPG Level Up Optimization

Steve is an avid MMORPG fan who has been playing World of Warcraft: Classic since day one. He is now just 2 levels away from reaching the maximum level. To level up, he must accumulate experience points (XP). The experience required for the first level‐up is \(s_1\) and for the second is \(s_2\). When Steve completes a task, he earns some XP and spends a certain amount of time. However, once he levels up, the same task (if not completed before leveling up) gives lower XP and takes less time.

More formally, you are given a list of \(n\) tasks. For each task \(i\), if performed before leveling up, Steve spends \(t_i\) minutes and earns \(x_i\) XP. If he performs it after leveling up, it takes \(r_i\) minutes and gives \(y_i\) XP instead. When Steve finishes a task, his accumulated XP is updated. If the XP reaches (or exceeds) the requirement for the current level-up, he immediately levels up. Moreover, any XP in excess of what was needed to level up is carried over toward the next level.

Note that each task can be completed at most once regardless of when it is done.

Your task is to determine the order in which Steve should complete tasks in order to reach the maximum level (i.e. complete both level-ups) in the shortest total time. If it is impossible to level up, output -1.

Formally:

• In phase 1 (before the first level-up), choose a subset of tasks. The sum of their pre‑upgrade XP, \(\sum_{i \in A} x_i\), must be at least \(s_1\). The total time cost will be \(\sum_{i \in A} t_i\). The excess XP \(\left(\sum_{i \in A} x_i - s_1\right)\) is carried over to the next phase.
• In phase 2 (after the first level-up), choose a subset of the remaining tasks. Their total post‑upgrade XP, \(\sum_{i \in B} y_i\), combined with the carried over XP, must reach at least \(s_2\). The time cost here is \(\sum_{i \in B} r_i\).

The objective is to minimize the total time \(\sum_{i \in A} t_i + \sum_{i \in B} r_i\) while satisfying:

[ \sum_{i \in A} x_i \ge s_1 \quad \text{and} \quad \left(\sum_{i \in A} x_i - s_1\right) + \sum_{i \in B} y_i \ge s_2. ]

inputFormat

The input consists of multiple integers separated by spaces and newlines. The first line contains three integers \(s_1\), \(s_2\), and \(n\) — the experience required for the first level-up, the experience required for the second level-up, and the number of tasks respectively.

Then follow \(n\) lines, each describing a task. The \(i\)-th line contains four integers:

• \(t_i\): time (in minutes) to complete task \(i\) if done before leveling up,
• \(x_i\): experience gained from task \(i\) if done before leveling up,
• \(r_i\): time (in minutes) to complete task \(i\) if done after leveling up,
• \(y_i\): experience gained from task \(i\) if done after leveling up.

outputFormat

Output a single integer — the minimum total time required for Steve to reach maximum level. If it is impossible to level up, output -1.

sample

10 10 3
5 8 1 6
5 7 2 5
3 3 1 2

9