시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 7 7 58.333%

문제

그렘린은 작고, 재미있고, 털이 보송보송한 상상 속의 요정이다. 그렘린의 종류는 N가지이며, 편의상 종류별로 1번 부터 N번까지 차례대로 번호가 매겨져있다.

T년 전 한 연구소에서 폭발이 일어나 N 종류의 그렘린이 한 마리씩 생겨났다. 그렘린은 두 단계의 성장 과정(알 → 성장기)을 지나 완전히 자란다.

종류가 i인 그렘린은 알에서 부화하고 Yi년 동안 성장기를 지난다. 성장을 완전히 마친 그렘린은 완전한 성장 직후 Ki개의 알을 낳는다. 각 알 별로 태어나는 그렘린 종류가 다를 수 있고, 알이 부화하는데 걸리는 시간도 다를 수 있다. 안타깝게도 그렘린은 알을 다 낳고 죽는다.

폭발이 일어나고 T년이 지난 현재, 과학자들은 여태까지 존재했던 그렘린 중에 조상이 가장 많은 그렘린이 궁금해졌다. 다만 과학자들은 아직 부화하지 않은 그렘린은 고려하지 않는다. 여기서 조상이란, 부모, 부모의 부모, 부모의 부모의 부모, ... 만 고려한다. 올해 부화 예정인 알들은 모두 부화되었다고 봐도 무방하다.

과학자들을 도와 가장 조상이 많은 그렘린의 조상수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 그렘린 종류의 수 N과 폭발이 일어난 뒤 지난 년 수 T가 주어진다. (1 ≤ N ≤ 100, 1 ≤ T ≤ 1015)

다음 3N개의 줄에 그렘린 종류에 대한 입력이 주어진다.

  • 첫 줄에는 자연수 Ki와 Yi가 주어진다. (1 ≤ Ki ≤ 1000, 1 ≤ Yi ≤ 1000)
    Ki는 부화하는 알의 개수이고, Yi는 i번 종류의 그렘린이 부화한 뒤 성장기를 거치는 기간을 의미한다.
  • 둘째 줄에는 각 알이 부화되고 나오는 그렘린의 종류를 나타내는 Ki개의 자연수가 주어진다.
  • 셋째 줄에는 각 알이 부화하는데 걸리는 년 수가 주어진다. 이는 1이상 1000 이하의 값이다.

출력

첫 줄에 가장 조상이 많은 그렘린의 조상의 수를 출력한다.

예제 입력

2 42
1 10
1
5
1 5
1
5

예제 출력

3

힌트

2번 종류 그렘린이 폭발이 일어난 뒤 5년째에 알을 낳고 죽는다.

그 알은 10년째에 부화되어 1번 종류 그렘린이 나온다. 이 그렘린은 20년째에 알을 낳고 죽는다.

그 알은 25년째에 부화되어 1번 종류 그렘린이 나온다. 이 그렘린은 35년째에 알을 낳고 죽는다.

그 알은 40년째에 부화되어 1번 종로 그렘린이 나온다. 이 그렘린의 조상의 수는 3이다.