import sys
input = sys.stdin.readline
while True:
N,A,B = map(int,input().split())
if not N:
break
balloon = [0]*N
diff = []
SUM = 0
for i in range(N):
k,a,b = map(int,input().split())
SUM += k*a
balloon[i] = k
diff.append((b-a,i))
A -= k
diff.sort()
i = 0
while i<N:
d,n = diff[i]
k = balloon[n]
if A+k > 0:
break
A += k
B -= k
SUM += d*k
i += 1
balloon[n] += A
SUM -= d*A
B += A
while i<N:
d,n = diff[i]
k = balloon[n]
if d>=0 or B-k<0:
break
B -= k
SUM += d*k
i += 1
if d<0:
SUM += d*B
print(SUM)
발상은 매우 쉬운데 구현이 살짝 까다로웠던 문제.
알고리즘을 요약하면,
1. 모든 팀의 풍선을 A에서 받았다고 가정하고 SUM을 구한 뒤, A에서 모든 풍선의 개수만큼 빼준다.
2. 모든 팀의 a와 b의 거리차(b-a)를 리스트로 만들고 정렬한다.
3. 거리차가 작은 순으로 A가 0이 될때까지 B에서 풍선을 받는다. SUM에서 거리차를 더해준다.
4. 남은 거리차가 음수면 B의 풍선이 다 닳지 않고, 거리차가 0보다 커지기 전까지 B에서 풍선을 받는다. SUM에서 거리차를 더해준다.
즉 쉽게 말해서 모든 풍선을 A에서 받은 뒤, 거리차를 기준으로 B에서 풍선을 차례대로 받는다고 생각하면 된다.
오늘의 교훈) 테스트케이스 개수를 주의하자