22811_Balloons

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 hosting site maintained two rooms, A and B, each containing a supply of balloons. There were N teams attending the contest, each sitting in different locations, some being closer to room A, and others to room B. Given the number of balloons needed by each team and each teams distance from room A and room B, 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 allocated in an optimal fashion from rooms A and B? For the purposes of this problem, assume that the contest staff were cheap and only bought one color of balloon.

There will be several test cases in the data file. Each test case will begin with a line with three integers:   N A B, where N is the number of teams ( 1 ≤ N ≤ 1000 ), and A and B are the number of balloons in rooms A and B, respectively ( 0 ≤ A, B ≤ 10000 ).

On each of the next N lines there will be three integers, representing information for each team:  K  D_A  D_B where K is the total number of balloons that this team will need, D_A is the distance of this team from room A, and D_B is this team's distance from room B ( 0 ≤ D_A, D_B ≤ 1000 ). You may assume that there are enough balloons -- that is, . The data file will end with a line with three 0s.

For each test case, output a single integer, representing the minimum total distance that must be traveled to deliver all of the balloons. Count only the outbound trip, from A or B to the team. Don't count the distance that a runner must travel to return to room A or room B. Print each integer on its own line with no spaces.

Do not print any blank lines between answers.

3 15 35
10 20 10
10 10 30
10 40 10
0 0 0

300