항공권 묶음 구매 기록

문제

여행 준비 담당자가 같은 날짜에 출발하는 항공권 K장을 구매하려 한다. 구매 화면에는 N개의 판매 창구가 있으며, 각 창구는 서로 다른 항공권 재고를 관리한다. 창구에는 처음 제시하는 가격 P, 한 장을 판매한 뒤 가격에 더하는 금액 D, 판매할 수 있는 최대 수량 C가 정해져 있다. 모든 가격과 증가 금액은 정수다. 한 창구에서 아직 항공권을 구매하지 않았다면 그 창구의 현재 가격은 P다. 그 창구에서 이미 t장을 구매했다면 다음 한 장의 현재 가격은 P+t×D다. 다만 t가 C와 같아지면 재고가 소진되어 더는 구매할 수 없다. 다른 창구에서 항공권을 구매해도 이 창구의 가격이나 재고는 바뀌지 않는다. 증가 금액이 0이면 재고가 남아 있는 동안 계속 같은 가격을 제시한다. 담당자는 한 번에 한 장씩 구매한다. 매번 재고가 남은 창구 중 현재 가격이 가장 낮은 창구를 선택한다. 현재 가격이 같은 창구가 여러 개라면 입력에서 먼저 나온 창구를 선택한다. 선택한 항공권의 현재 가격을 지불한 뒤, 해당 창구의 판매 수량을 한 장 늘린다. 가격을 올리기 전의 금액을 지불한다는 점에 유의한다. 이 절차를 정확히 K번 수행했을 때 지불한 금액의 합을 구한다. 구매를 시작할 때 보이던 가격으로 여러 장을 한꺼번에 예약할 수는 없다. 전체 재고가 K장보다 적다면 필요한 수량을 채울 수 없으므로 합계 대신 -1을 출력한다. 창구 번호는 입력 순서대로 1번부터 N번까지이며, 별도의 수수료나 할인은 없다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1≤N≤10,000, 1≤K≤200,000이다.
다음 N개 줄에는 창구 번호 순서대로 정수 P, D, C가 주어진다. 1≤P≤1,000,000, 0≤D≤1,000, 1≤C≤200,000이다.

출력

정해진 절차로 항공권 K장을 구매할 수 있으면 총 지불 금액을 정수로 출력한다. 구매할 수 없으면 -1을 출력한다.

2 5
10 3 2
12 0 3

59

1 3
7 2 2

-1

3 4
5 0 2
5 1 2
8 0 1

21

출처: Devin.KR 자체 제작