На рівень вгору
Будучи фанатом 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, якщо немає можливості виконати квести для проходження обох рівнів.