Кулі
Як ви знаєте, під час цього конкурсу командам роздають повітряні кулі, коли вони вирішують задачі. Однак у минулому це іноді створювало складні логістичні проблеми.
Один із майданчиків проведення конкурсу мав дві кімнати, A та B, кожна з яких містила запас повітряних куль. На конкурсі було N команд, кожна з яких сиділа в різних місцях: деякі ближче до кімнати A, а інші до кімнати B. Враховуючи кількість куль, необхідних кожній команді, та відстань кожної команди від кімнати A та кімнати B, яка мінімальна загальна можлива відстань, яку повинні подолати всі кулі, коли їх доставляють до відповідних команд, за умови, що вони розподілені оптимальним чином з кімнат A та B? Для цілей цієї задачі припустимо, що організатори конкурсу були економними і купили лише один колір куль.
Вхідні дані
У файлі даних буде кілька тестових випадків. Кожен тестовий випадок починатиметься з рядка з трьома цілими числами:
N A B
де N — кількість команд (1 ≤ N ≤ 1000), а A та B — кількість куль у кімнатах A та B відповідно (1 ≤ A, B ≤ 10000).
На кожному з наступних N рядків буде три цілі числа, що представляють інформацію для кожної команди:
K D_A D_B
де K — загальна кількість куль, які потрібні цій команді, D_A — відстань цієї команди від кімнати A, а D_B — відстань цієї команди від кімнати B (1 ≤ D_A, D_B ≤ 1000). Ви можете припустити, що куль достатньо - тобто, ∑_i K_i ≤ A + B. Файл даних закінчиться рядком з трьома 0.
Вихідні дані
Для кожного тестового випадку виведіть одне ціле число, яке представляє мінімальну загальну відстань, яку потрібно подолати для доставки всіх куль. Рахуйте лише шлях в один бік, від A або B до команди. Не рахуйте відстань, яку повинен подолати кур'єр, щоб повернутися до кімнати A або B. Надрукуйте кожне ціле число в окремому рядку без пробілів. Не друкуйте жодних порожніх рядків між відповідями.