Будучи фанатом MMORPG, Стив был очень взволнован, когда появился анонс World of Warcraft Classic. Он начал играть с первого дня, и теперь ему осталось пройти всего два уровня до максимального уровня. Конечно, у него не так много времени, как было при первом появлении игры, поэтому он очень хочет пройти эти два уровня как можно быстрее.

Чтобы пройти первый уровень, Стиву нужен опыт s1. Только после того как он его получит, он сможет перейти на второй уровень, на котором ему следует получить опыт s2 для его прохождения.

У Стива имеется список из n доступных квестов. Он знает, что может закончить два уровня используя эти квесты. Чтобы пройти i-й квест, Стиву нужно ti минут. В результате за него он получит xi опыта.

Когда Стив завершает квест, который переводит его на следующий уровень, дополнительно полученный опыт вычитается из опыта следующего уровня. Как только он повысит уровень, все оставшиеся квесты будут давать меньший опыт yi, но они также потребуют меньше времени ri.

Обратите внимание, что если Стив завершит квест, то он больше не сможет его повторить (даже на другом уровне).

По имеющемуся списку квестов помогите Стиву выбрать порядок, в котором он будет их выполнять, чтобы пройти последние два уровня как можно быстрее.

Входные данные

Первая строка содержит три целых числа n, s1, s2 (1 ≤ n, s1, s2 ≤ 500) - количество квестов, необходимый опыт для первого уровня и необходимый опыт для второго уровня.

Каждая из следующих n строк содержит четыре целых числа xi, ti, yi, ri (1 ≤ yi < xi ≤ 500, 1 ≤ ri < ti ≤ 109), где xi и yi - опыт который Вы получите от i-го квеста на 1-м и 2-м уровне соответственно, а ti и ri это количество минут которое необходимо потратить, чтобы пройти этот квест на 1-м и 2-м уровне соответственно.

Выходные данные

Выведите одно число - минимальное количество минут, которое нужно Стиву, чтобы пройти два уровня, или -1, если нет возможности выполнить квесты для прохождения обоих уровней.