시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB151161413.725%

문제

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

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

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

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

입력

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

둘째 줄부터 N개의 줄에 각 팀이 획득한 금메달, 은메달, 동메달의 개수가 1번 팀부터 순서대로 주어진다. 각 팀이 획득한 금메달, 은메달, 동메달의 수는 각각 10,000개 이하인 음이 아닌 정수이다.

입력으로 주어지는 금메달 수의 합, 은메달 수의 합, 동메달 수의 합은 여러가지 올림픽 사정으로 인해 같지 않을 수도 있다. 하지만, 남은 L경기에서는 이런 경우 없이 모든 메달이 수여된다.

출력

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

예제 입력 1

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

예제 출력 1

4

예제 입력 2

3 1
0 0 0
1 0 0
1 0 0

예제 출력 2

3

예제 입력 3

3 2
0 0 0
1 0 0
1 0 0

예제 출력 3

1

예제 입력 4

3 6
0 7 6
6 0 0
6 1 1

예제 출력 4

1

예제 입력 5

3 5
0 5 5
5 0 0
5 0 10

예제 출력 5

2

예제 입력 6

7 3
0 1 1
3 0 0
3 0 0
3 0 1
3 1 0
3 1 1
3 1 1

예제 출력 6

5

힌트

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

출처