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