동전 수집가

어느 나라에서는 N가지 액면의 동전이 통용되고 있으며, 그중 가장 작은 것은 1센트 동전이다. 또한 모든 동전보다 값이 큰 K센트짜리 지폐가 있다. 어떤 동전 수집가는 각 액면의 동전을 하나씩 모으려고 한다. 그는 이미 집에 몇 종류의 동전을 가지고 있으며, 지금 지갑에는 K센트 지폐 한 장만 들고 있다.

그는 1센트부터 K-1센트까지 모든 가격의 물건을 파는 상점에 있다. 이 상점은 거스름돈을 다음 알고리즘으로 내어 준다.

1. 남은 거스름돈을 A센트라고 하자.
2. A를 넘지 않는 가장 큰 액면을 찾는다. 이를 B센트 동전이라고 하자.
3. B센트 동전 한 개를 손님에게 주고 A를 B만큼 줄인다.
4. A = 0이면 종료하고, 그렇지 않으면 2번으로 돌아간다.

수집가는 물건 하나를 사고 K센트 지폐로 값을 치른다. 다음을 구하여라.

• 이 한 번의 구매에서 받는 거스름돈으로 새로 얻을 수 있는, 아직 가지고 있지 않은 서로 다른 액면의 최대 개수
• 거스름돈에 그 최대 개수만큼의 새로운 액면이 포함되도록 하면서 살 수 있는 물건의 가장 비싼 가격

첫째 줄에 두 정수 N (1 ≤ N ≤ 500000)과 K (2 ≤ K ≤ 1000000000)가 주어진다. 다음 N개의 줄에는 각 액면의 정보가 주어지는데, (i+1)번째 줄에는 두 정수 c_i (1 ≤ c_i < K)와 d_i가 주어진다. 여기서 c_i는 동전의 값(센트)이고, d_i는 수집가가 이미 이 동전을 가지고 있으면 1, 가지고 있지 않으면 0이다. 동전은 값이 엄격히 증가하는 순서로 주어지며(c_1 < c_2 < ... < c_N), 첫 번째 동전은 1센트 동전이다(c_1 = 1).

두 줄을 출력한다. 첫째 줄에는 수집가가 아직 가지고 있지 않지만 한 번의 구매로 얻을 수 있는 액면의 최대 개수를 정수 하나로 출력한다. 둘째 줄에는 거스름돈에 그 최대 개수만큼의 새로운 액면이 포함되도록 하면서 살 수 있는 물건의 가장 비싼 가격을 정수 하나로 출력한다.