시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 46 8 8 21.622%

문제

N개의 팀이 프로그래밍 올림픽에 참가했다. 각 팀은 1번부터 N번까지 번호가 매겨져 있다. 올림픽 규칙에 따라서, 올림픽은 여러 개의 경기로 이루어져 있다. 각 경기가 끝날 때마다 상위 세 팀은 순위에 따라 금, 은, 동메달을 받게 된다. 한 경기에서 동점을 기록하는 경우는 없고, 각 팀은 경기당 최대 1개의 메달을 받을 수 있다. 올림픽이 끝나면, 다음과 같은 규칙을 이용해 최종 순위를 매긴다.

  1. 두 팀의 금메달 수가 다르면, 금메달을 많이 가진 팀이 등수가 높다. 같은 경우에는 2번 규칙을 따른다.
  2. 두 팀의 은메달 수가 다르면, 은메달을 많이 가진 팀이 등수가 높다. 같은 경우에는 3번 규칙을 따른다.
  3. 두 팀의 동메달 수가 다르면, 동메달을 많이 가진 팀이 등수가 높다. 같은 경우에는 팀 번호가 작은 팀의 등수가 높다.

아직 올림픽은 끝나지 않았고, 총 L개의 경기가 남아있다. 이 상황에서 각 팀이 획득한 메달의 수가 주어진다. 1번 팀이 남은 L경기에서 모두 금메달은 딴다고 했을 때, 1번 팀이 기록할 수 있는 가장 낮은 등수를 구하는 프로그램을 작성하시오. 

가장 높은 등수는 1이고, 그 다음 등수는 2이다. 이런식으로 등수를 계산할 수 있다.

 

입력

첫째 줄에 팀의 수 N(3 ≤ N ≤ 100)과 남은 경기 수 L(0 ≤ L ≤ 10,000)이 주어진다. 

둘째 줄부터 N개의 줄에 각 팀이 획득한 금메달, 은메달, 동메달의 개수가 1번 팀부터 순서대로 주어진다.

출력

첫째 줄에 1번 팀이 기록할 수 있는 가장 낮은 등수를 출력한다.

예제 입력

6 6
1 2 3
100 0 0
7 0 0
7 0 0
7 0 0
7 0 0

예제 출력

4

힌트

금메달의 개수가 너무 많이 차이나기 때문에, 1번 팀은 항상 2번 팀보다 등수가 낮다. 나머지 두 팀이 남은 경기에서 은메달을 3개씩 받는다면, 1번 팀은 그 두 팀보다 등수가 낮게되고 4등을 기록하게 된다.

출처