Balloons#1381
As you know, balloons are handed out during this contest to teams as they solve problems. However, in the past this has sometimes presented challenging logistical problems.
One contest site had two rooms, and , each containing a supply of balloons. There were teams at the contest, each sitting in different locations, some closer to room , others closer to room . Given the number of balloons each team needs, and the distance of each team from room and room , what is the minimum total possible distance that must be traveled by all balloons as they are delivered to their respective teams, assuming they are distributed optimally from rooms and ? For this problem, assume that the contest staff were cheap and bought only one color of balloon.
There are several test cases in the data file. Each test case begins with a line containing three integers:
where is the number of teams (1 \le N \le 1000), and and are the number of balloons in rooms and (1 \le A, B \le 10000).
Each of the next lines contains three integers for each team:
D_A D_B
where is the total number of balloons needed by this team, D_A is the distance from room , and D_B is the distance from room (1 \le D_A, D_B \le 1000). You may assume there are enough balloons: \sum_i K_i \le A + B. The data file ends with a line containing three .
For each test case, output a single integer representing the minimum total distance required to deliver all the balloons. Count only the outbound trip, from or to the team. Do not count the return trip to room or . Print each integer on its own line with no spaces. Do not print blank lines between answers.
Example 1