스터디 시간 정하기 1

의찬이는 여러 참가자를 모아 알고리즘 대회 준비 스터디를 진행하려고 한다. 참가자는 많이 모였지만 각자 가능한 시간이 달라서 의찬이는 스터디 시간을 정하기가 어렵다. 의찬이는 바쁘면서도 한가하기 때문에 최대한 다른 참가자의 시간에 맞춰 스터디를 진행하려고 한다. T시간 동안 스터디를 진행할 때 참가자들의 시간 만족도를 구해, 시간 만족도가 최대인 시간을 찾으려고 한다.

시간 만족도는 스터디 시간 동안 각 참가자가 참여할 수 있는 시간의 합이다.

예를 들어 스터디를 4시간 동안 진행하려 하고 1번, 2번, 3번 참가자의 가능한 시간이 아래 그림과 같다고 하자.

<그림 1> 참가자별로 스터디가 가능한 시간 예시

1번 참가자는 시각 0부터 시각 6까지의 시간에 스터디가 가능하다.

2번 참가자는 시각 1부터 시각 3까지, 시각 4부터 시각 6까지의 시간에 스터디가 가능하다.

3번 참가자는 시각 4부터 시각 8까지의 시간에 스터디가 가능하다.

스터디를 시각 2부터 시각 6까지 진행한다면 시간 만족도는 4 + (1 + 2) + 2 = 9가 되며, 이는 시간 만족도가 최대인 시간이다.

참가자들이 스터디에 참여할 수 있는 시간을 입력받아 시간 만족도가 최대인 시간을 찾아 출력한다. 시간 만족도가 최대인 시간이 여러 개라면 시작 시간이 가장 빠른 시간을 출력한다.

첫째 줄에는 스터디에 참가하려는 참가자 수 N과 스터디 시간 T가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 100,000)

다음 줄부터 참가하려는 참가자의 시간 정보가 N개 주어진다.

각 정보의 첫째 줄에는 가능한 시간의 수 K가 주어진다. K는 1 이상의 자연수이고 입력받은 모든 K의 합은 500,000을 넘지 않는다.

각 정보의 둘째 줄부터 K개의 줄에 걸쳐 가능한 시간의 시작 시각 Si와 끝나는 시각 Ei가 주어진다. 이때 Ei < Si+1 (1 ≤ i < K)을 만족한다. (0 ≤ Si < Ei ≤ 100,000)

시간 만족도가 최대인 시간을 찾아 시작 시각과 끝나는 시각을 공백 한 칸을 사이에 두고 출력한다. 시간 만족도가 최대인 시간이 여러 개라면 시작 시간이 가장 빠른 시간을 출력한다.