시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 55 12 9 31.034%

문제

가톨릭대학교 정문에 살고있는 곱등이 재홍이가 여름을 나기 위해 손 선풍기를 사려고 바이마트에 도착했다.

손 선풍기는 1번부터 N번까지 총 N개가 진열되어 있고, 모두 특별한 작동방식을 가지고 있다.

손 선풍기는 작동 시킨 후 K 초 마다 비용을 추가 결제해야 손 선풍기가 계속 돌아가는데, 이때 손 선풍기가 요구하는 비용은 K초가 흘렀을 때 C만큼의 비용을, 2✕K 초가 흘렀을 경우 추가적으로 2✕C의 비용을, t를 자연수라고 할 때,tK 초가 흘렀을 경우 추가적으로 tC의 비용을 지불해야 한다.

예를 들어 선풍기의 가격 P가 500, 추가요금을 지불해야하는 시간 단위 K가 3, 초기 추가비용 C가 100인 값을 가지는 손 선풍기를 가지고 있고 집까지 12의 시간이 걸린다면

3초에서 추가적으로 100의 비용이

6초에서 추가적으로 200의 비용이

9초에서 추가적으로 300의 비용이

12초에는 집에 도착했으므로 추가비용이 발생하지 않고 손 선풍기를 끈다.

따라서 600의 추가비용에 선풍기 가격 500을 더해 1100원의 비용이 발생한다.

재홍이는 집으로 돌아갈 때 손 선풍기가 없다면 도저히 돌아갈 수 없다고 판단하여 무조건 한 개의 선풍기를 구매하려고 한다. 재홍이가 집까지 돌아가는 시간이 주어졌을 때 집까지 돌아가는 동안 최소의 지출로 집까지 안전하게 돌아갈 수 있는 선풍기를 고르는 것을 도와주자.

입력

첫 줄에 진열된 손 선풍기의 개수 N(1 ≤ N ≤ 100,000) 과 재홍이가 집까지 가는데 걸어가는 시간 Q(1 ≤ Q ≤ 100,000,000)가 주어진다.

두 번째 줄부터 N+1번째 줄까지 세 정수 P, K, C가 주어지는데 P(0 ≤ P ≤ 100,000)는 손 선풍기의 가격, K(1 ≤ K ≤ 100,000,000)는 추가비용을 지불해야하는 시간 간격, C(1 ≤ C ≤ 1,000,000)는 추가비용의 초기 값을 의미한다.

출력

N개의 손 선풍기 중 재홍이가 최소의 비용으로 집을 도착하기 위해 사야 하는 손 선풍기의 번호와 그때의 필요한 비용을 출력한다.

같은 비용으로 갈 수 있다면 더 작은 번호의 손 선풍기의 번호와 비용을 출력한다. 모든 선풍기의 최종 비용값은 264 보다 작다.

예제 입력 1

5 12
100 2 100
200 3 100
0 10 500
0 10 600
1000 13 100

예제 출력 1

3 500