스터디 시간 정하기 2

의찬이는 여러 참가자를 모아 알고리즘 대회 준비 스터디를 열려고 한다. 참가자는 많이 모였지만 각자 가능한 시간이 달라서 의찬이는 스터디 시간을 정하지 못하고 있다. 의찬이는 바쁘기도 하고 한가하기도 해서, 다른 참가자들의 시간에 최대한 맞춰 스터디를 진행하려고 한다. 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 ≤ 1000, 1 ≤ T ≤ 1000)

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

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

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

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