올림픽 순위

N개의 팀이 프로그래밍 올림픽에 참가한다. 팀 번호는 1번부터 N번까지이다.

올림픽은 여러 경기로 이루어진다. 각 경기가 끝날 때마다 1위, 2위, 3위 팀은 각각 금메달, 은메달, 동메달을 받는다. 한 경기 안에서는 동점이 없으며, 한 팀은 그 경기에서 최대 하나의 메달만 받을 수 있다.

대회가 끝난 뒤 순위는 다음 순서로 정한다.

1. 금메달 수가 많은 팀이 더 높은 순위를 얻는다.
2. 금메달 수가 같으면 은메달 수가 많은 팀이 더 높은 순위를 얻는다.
3. 금메달과 은메달 수가 모두 같으면 동메달 수가 많은 팀이 더 높은 순위를 얻는다.
4. 세 종류의 메달 수가 모두 같으면 팀 번호가 작은 팀이 더 높은 순위를 얻는다.

아직 L개의 경기가 남아 있고, 현재 각 팀의 메달 수가 주어진다. 남은 모든 경기에서 1번 팀이 금메달을 받는다고 하자. 남은 경기의 은메달과 동메달을 적절히 배정했을 때, 1번 팀이 얻을 수 있는 가장 낮은 최종 순위를 구하시오.

가장 높은 순위는 1등이고, 그다음은 2등이다.

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

다음 N개의 줄에는 1번 팀부터 N번 팀까지, 각 팀이 현재 가진 금메달 수, 은메달 수, 동메달 수가 차례로 주어진다. 각 수는 0 이상 10,000 이하의 정수이다.

현재까지의 금메달 총합, 은메달 총합, 동메달 총합은 서로 다를 수 있다. 단, 남은 L개의 경기에서는 매 경기 금메달, 은메달, 동메달이 모두 수여된다.

첫째 줄에 1번 팀이 얻을 수 있는 가장 낮은 최종 순위를 출력한다.

금메달 수 차이가 너무 커서 1번 팀은 어떤 배정에서도 2번 팀보다 낮은 순위가 된다. 또한 금메달 수가 같아질 수 있는 팀들 가운데 두 팀이 남은 경기에서 은메달을 충분히 받으면 1번 팀보다 높은 순위가 될 수 있다. 이 경우 1번 팀의 최종 순위는 4등까지 내려간다.