항공권 검색의 가격 상한

문제

여행 준비 모임에서 같은 구간의 항공권을 여러 장 구입하려 한다. 모임은 출발 날짜와 시간에 여유가 있으므로 검색에 등록된 항공권 중 어느 것을 골라도 된다. 검색 서비스에는 N개의 판매 묶음이 등록되어 있으며, 각 묶음에 들어 있는 항공권의 가격은 간단한 규칙으로 정해져 있다. 묶음 i에는 항공권이 c_i장 들어 있다. 이 묶음의 항공권을 가격이 낮은 순서로 나열했을 때, j번째 항공권의 가격은 a_i+(j-1)d_i이다. 여기서 j는 1 이상 c_i 이하의 정수다. a_i는 묶음의 가장 낮은 가격이고, d_i는 이웃한 두 항공권 사이의 가격 차이다. d_i가 0일 수도 있으며, 이때 해당 묶음의 항공권은 모두 같은 가격이다. 묶음은 항공권 정보를 압축하여 표현하는 단위일 뿐이다. 한 묶음을 통째로 구입할 필요는 없고, 그 안에서 원하는 항공권만 골라 구입할 수 있다. 서로 다른 묶음의 항공권은 서로 다른 좌석이며, 같은 묶음 안에서도 각각 별개의 좌석이다. 가격이 같다는 이유로 좌석을 하나로 합치지 않는다. 각 좌석은 최대 한 번만 구입할 수 있다. 모임은 검색 화면에 정수 가격 상한 P를 설정하려 한다. 그러면 모든 묶음에서 가격이 P 이하인 항공권만 화면에 표시된다. 표시된 항공권이 K장 이상이면 그중 K장을 골라 구입할 수 있다. 이 조건을 만족하는 가장 작은 0 이상의 정수 P를 구한다. P는 K장의 가격 합계가 아니라 항공권 한 장에 적용되는 상한이다. 같은 가격의 항공권이 여러 장 표시되면 그중 어느 좌석을 골라도 된다. 실제로 고른 좌석이나 묶음 번호는 출력하지 않는다. 모든 묶음의 좌석 수를 합해도 K장보다 적다면 가격 상한을 아무리 높여도 구입할 수 없으므로 -1을 출력한다.

입력

첫째 줄에 판매 묶음의 수 N과 필요한 항공권 수 K가 공백으로 구분되어 주어진다.
다음 N개 줄의 i번째 줄에 a_i, d_i, c_i가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 15,000, 1 ≤ K ≤ 10^12, 1 ≤ a_i ≤ 1,000,000, 0 ≤ d_i ≤ 1,000,000, 1 ≤ c_i ≤ 1,000,000이다.

출력

항공권을 K장 이상 표시하는 가장 작은 가격 상한 P를 한 줄에 출력한다. 전체 항공권 수가 K보다 작으면 -1을 출력한다.

3 6
10 4 3
7 0 2
9 5 2

14

2 5
3 2 2
8 0 2

-1

2 4
5 0 6
1 3 3

5

출처: Devin.KR 자체 제작