Будучи фанатом MMORPG, Стив был очень взволнован, когда появился анонс World of Warcraft Classic. Он начал играть с первого дня, и теперь ему осталось пройти всего два уровня до максимального уровня. Конечно, у него не так много времени, как было при первом появлении игры, поэтому он очень хочет пройти эти два уровня как можно быстрее.
Чтобы пройти первый уровень, Стиву нужен опыт s[1]
. Только после того как он его получит, он сможет перейти на второй уровень, на котором ему следует получить опыт s[2]
для его прохождения.
У Стива имеется список из n доступных квестов. Он знает, что может закончить два уровня используя эти квесты. Чтобы пройти i-й квест, Стиву нужно t[i]
минут. В результате за него он получит x[i]
опыта.
Когда Стив завершает квест, который переводит его на следующий уровень, дополнительно полученный опыт вычитается из опыта следующего уровня. Как только он повысит уровень, все оставшиеся квесты будут давать меньший опыт y[i]
, но они также потребуют меньше времени r[i]
.
Обратите внимание, что если Стив завершит квест, то он больше не сможет его повторить (даже на другом уровне).
По имеющемуся списку квестов помогите Стиву выбрать порядок, в котором он будет их выполнять, чтобы пройти последние два уровня как можно быстрее.
Первая строка содержит три целых числа n, s[1]
, s[2]
(1 ≤ n, s[1]
, s[2]
≤ 500) - количество квестов, необходимый опыт для первого уровня и необходимый опыт для второго уровня.
Каждая из следующих n строк содержит четыре целых числа x[i]
, t[i]
, y[i]
, r[i]
(1 ≤ y[i]
< x[i]
≤ 500, 1 ≤ r[i]
< t[i]
≤ 10^9
), где x[i]
и y[i]
- опыт который Вы получите от i-го квеста на 1-м и 2-м уровне соответственно, а t[i]
и r[i]
это количество минут которое необходимо потратить, чтобы пройти этот квест на 1-м и 2-м уровне соответственно.
Выведите одно число - минимальное количество минут, которое нужно Стиву, чтобы пройти два уровня, или-1, если нет возможности выполнить квесты для прохождения обоих уровней.