题目描述

作为一个 MMORPG 粉，得知《魔兽世界：经典旧世》发布的 Steve 非常兴奋。他从发布的第一天就开始玩，现在离满级只差 $2$ 级了。当然，他现在没有刚开始玩那时那么有空，因此他想尽快升到满级。

升第一个等级需要 $s_1$ 经验值。只有当他获得了这么多经验后，才能升到下一级，而第二个等级又需要 $s_2$ 经验值来升级。

Steve 有一个有 $n$ 个任务的任务列表。他希望通过完成一些任务来升到满级。Steve 需要花 $t_i$ 分钟才能完成第 $i$ 个任务，这个任务会让他获得 $x_i$ 经验值。

当 Steve 完成了一个任务后可以升级了，超过升级所需的那部分经验值将会计入下一等级。当他升了一级之后，第 $i$ 个任务可获得的经验值会减少为 $y_i$，而完成任务的时间也会减为 $r_i$。

需要注意的是，Steve 完成了的任务不能重复接取，无论是否升级。

已知任务列表中的任务信息，帮助 Steve 找出一个完成任务的顺序，使得他升到满级所需的时间最短。

输入格式

第一行包含三个整数 $n, s_1, s_2 \ (1 \leq n, s_1, s_2 \leq 500)$，代表任务的数量、升第一级所需的经验值和升第二级所需的经验值。

接下来的 $n$ 行每行包含四个整数 $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)$，代表第 $i$ 个任务获得的经验值、完成所需的时间、升一级之后获得的经验值和完成所需的时间。

输出格式

输出一个整数，代表 Steve 升到满级所需的最短时间的分钟数，如果无论如何都无法升到满级，输出 $-1$。

2 100 100
100 100 10 10
101 11 100 10

110

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

40

2 20 5
10 10 5 5
10 10 5 5

-1