Воздушные шары
Как вы знаете, во время этого конкурса командам раздают воздушные шары по мере решения задач. Однако в прошлом это иногда вызывало сложные логистические проблемы.
Одна из площадок проведения конкурса содержала две комнаты, 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. Выведите каждое целое число на отдельной строке без пробелов. Не выводите пустые строки между ответами.