Lola의 일정

Lola는 관심사가 많은 활발한 소녀로, 하루하루가 그녀에게 가능성으로 가득 차 있고 그녀가 기꺼이 참여할 흥미로운 활동들로 넘쳐난다. 아쉽게도 Lola가 참여하는 활동 중 상당수는 밀폐된 공간에서 이루어지며, 그 탓에 그녀의 비타민 D 수치는 이상적인 수준보다 약간 낮다. 이를 돕기 위해 의사는 그녀가 X분마다 매일 복용해야 하는 비타민 보충제를 처방했다.

Lola는 자신의 활동을 기록하는 앱을 만들었다. 이 앱의 주요 기능은 활동 일정 관리다. 각 활동은 제목과 시작 시각, 종료 시각으로 이루어진다. 이 앱은 또한 한 번만 울리는 알림과 반복 알림을 만들 수 있는데, 한 번만 울리는 알림은 제목과 알림을 한 번 받을 시각으로 구성되고, 반복 알림은 제목과 첫 알림 시각, 그리고 반복 주기로 구성된다. 보충제를 산 뒤 Lola는 X분마다 반복되는 반복 알림을 앱에 추가해서 보충제를 복용할 때마다 알림을 받고자 한다. 이상적으로는 활동 중에 보충제를 복용하지 않는 것이 좋다. 이렇게 빡빡한 일정 속에서 그녀는 복용을 시작할 이상적인 시각을 정하기가 어렵다.

당신의 임무는 Lola가 보충제를 산 뒤 처음 복용할 이상적인 시각 T를 정하도록 돕는 것이다. 시각 T가 이상적이라는 것은, Lola가 보충제를 산 시각으로부터 최대 8시간 이내이고, 그녀가 복용해야 하는 시각 중 활동과 겹치는 횟수가 최소이며, 같은 횟수의 충돌을 낳으면서 T보다 이른 시각은 존재하지 않는다는 뜻이다.

명확히 하기 위해, Lola가 30분마다 보충제를 복용해야 하고, 어느 날 10:00에 보충제를 샀으며, 그날 18:00부터 18:30까지 예정된 활동이 하나 있다고 하자. 만약 그녀가 곧바로 처음 복용하기로 하면 10:00, 10:30, ..., 17:30, 18:00, 18:30, ...에 복용하게 된다. 따라서 활동과 두 번 충돌한다(하나는 18:00, 다른 하나는 18:30).

Lola는 8시간 제한 때문에 활동이 끝날 때까지 기다렸다가 처음 복용할 수는 없지만, 7시간 59분을 기다리면 충돌 횟수를 줄일 수 있다. 그렇게 하면 17:59, 18:29, 18:59, ...에 복용하게 되어 18:29에서 한 번만 충돌한다. 훨씬 낫지 않은가? 그러나 이것은 이상적이지 않은데, 같은 한 번의 충돌을 낳으면서 더 이른 시각이 있기 때문이다. 즉 1분을 기다려 10:01에 처음 복용하면 18:01에서 한 번 충돌한다. 충돌을 완전히 피할 수는 없으므로 이 경우 이상적인 시각은 보충제를 산 뒤 1분 후에 처음 복용하는 것이다.

Lola가 만든 앱에서 내보낸 활동 목록이 주어지며, 여기에는 보충제를 산 시각 이후에 시작하는 모든 활동에 대한 정보가 들어 있다. Lola는 이미 데이터를 전처리해 두었고, 각 활동은 보충제를 산 시각으로부터의 분 단위 시간과 분 단위 지속 시간으로 주어진다.

첫째 줄에는 두 정수 N (1 ≤ N ≤ 104)과 X (1 ≤ X ≤ 720)가 주어지며, 이는 Lola가 앱에서 내보낸 예정된 활동이 N개 있고 X분마다 보충제를 복용해야 함을 나타낸다. 다음 N개 줄 각각은 두 정수 S와 D (1 ≤ S, D ≤ 105)로 활동 하나를 설명하며, 이는 활동이 보충제를 산 뒤 S분 후에 시작하고 지속 시간이 D분임을 나타낸다. 활동은 서로 겹치지 않는다. 즉 서로 다른 두 활동이 주어졌을 때 한 활동이 다른 활동이 시작하기 전에 엄격히 끝나거나 그 반대다.

한 줄에 두 정수 T와 C를 출력한다. 각각 보충제를 처음 복용할 이상적인 시각을 보충제를 산 뒤 지난 분 단위로 나타낸 값과, 이 시각에 보충제를 복용할 때 생기는 충돌 횟수다.