作为一名 MMORPG 的粉丝，Steve 对《魔兽世界》经典怀旧服的发布感到非常兴奋。他从第一天就开始玩，现在距离满级只剩下最后两级了。当然，他不像游戏刚发布时那样有那么多时间，所以他非常希望能尽快完成这两级。

为了通过第一级，Steve 需要 $s_1$ 点经验值。只有在获得这些经验值后，他才能进入第二级，在第二级中他还需要获得 $s_2$ 点经验值才能通过。

Steve 有一份包含 $n$ 个可用任务的列表。他知道他可以通过这些任务完成这两级。完成第 $i$ 个任务需要 $t_i$ 分钟，完成后他将获得 $x_i$ 点经验值。

当 Steve 完成一个让他升级的任务时，多出的经验值溢出部分会从下一级所需的经验值中扣除。一旦他升级，所有剩余的任务提供的经验值都会变为 $y_i$，但完成它们所需的时间也会变为 $r_i$。

注意，如果 Steve 完成了一个任务，他就不能再重复完成该任务（即使是在另一个等级中）。

给定任务列表，请帮助 Steve 选择完成任务的顺序，以便尽快完成最后两级。

输入格式

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

接下来的 $n$ 行，每行包含四个整数 $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$)，其中 $x_i$ 和 $y_i$ 分别是第 $i$ 个任务在第一级和第二级获得的经验值，$t_i$ 和 $r_i$ 分别是第 $i$ 个任务在第一级和第二级完成所需的时间（分钟）。

输出格式

输出一个数字，表示 Steve 完成两级所需的最少分钟数；如果无法完成任务以通过两级，则输出 $-1$。

样例

输入 1

2 100 100
100 100 10 10
101 11 100 10

输出 1

110

输入 2

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

输出 2

40

输入 3

2 20 5
10 10 5 5
10 10 5 5

输出 3

-1