Balloons

Time limit1sMemory limit128 MB

Summary

Assign each team's balloons from rooms A and B, respecting supply limits, to minimize total travel distance.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Teams that solve a problem at a programming contest receive balloons. Because the balloons must be attached by hand, volunteers are needed.

The balloons are stored in room $A$ and room $B$ . A total of $N$ teams take part in the contest, and every team sits in a different place. Some teams are closer to room $A$ , others are closer to room $B$ .

For each team you are given the number of balloons it must receive and its distance from room $A$ and from room $B$ . Compute the minimum total travel distance required to attach all balloons. Assume there are plenty of volunteers, and that a team may receive several balloons of the same color. The distance to attach one balloon equals the distance from the room the balloon was taken from to that team. A volunteer can carry only one balloon at a time.

Input

The input consists of several test cases. The first line of each test case contains the number of teams $N$ ( $1 \le N \le 1000$ ) and the numbers of balloons stored in room $A$ and room $B$ , namely $A$ and $B$ ( $0 \le A, B \le 10000$ ).

Each of the next $N$ lines contains the number of balloons $K$ a team must receive, its distance $D_A$ from room $A$ , and its distance $D_B$ from room $B$ ( $0 \le D_A, D_B \le 1000$ ). Balloons are never insufficient; that is, $\sum K_i \le A + B$ in every test case.

The last line of the input contains three zeros and is not processed.

Output

For each test case, print on its own line the minimum total travel distance needed to attach balloons to all teams. Do not include the distance for returning to room $A$ or $B$ after attaching a balloon; count only the distance from a room to a team.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
1 5 0
5 3 7
0 0 0
```
Expected output
```
15
```