18130번 - 여름나기

가톨릭대학교 다솔관에 살고있는 현석이가 여름을 나기 위해 손 선풍기를 사려고 바이마트에 도착했다. 손 선풍기는 1번부터 N번까지 총 N개가 진열되어 있고, 모두 특별한 작동방식을 가지고 있다.

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

예를 들어 선풍기의 가격이 500원, 3시간마다 100원의 추가비용 값을 가지는 손 선풍기를 가지고 있고 집까지 12시간이 걸린다면, 3시간에서 100원이, 6시간에서 200원이, 9시간에서 300원이 12시간에는 집에 도착했으므로 추가비용이 발생하지 않고 손 선풍기를 끈다. 따라서 600원의 추가비용에 선풍기 가격 500원을 더해 1,100원의 비용이 발생한다.

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

첫 줄에 두 정수 진열된 손 선풍기의 개수 N(1 ≤ N ≤ 10,000) 와 현석이가 집까지 가는데 걸어가는 시간 Q(1 ≤ Q ≤ 1,000,000)가 주어진다.

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

N개의 손 선풍기 중 현석이가 최소의 비용으로 집을 도착하기 위해 사야 하는 손 선풍기의 번호와 그때의 필요한 비용을 공백으로 구분하여 출력한다. 답이 여러 개라면 손 선풍기의 번호가 더 작은 것을 출력한다.

어떤 선풍기를 쓰더라도 필요한 비용은 2⁶³-1 보다 작다.