Olympic Ranking

Time limit2sMemory limit128 MB

Summary

Given current medal counts, decide how to award all remaining silver and bronze medals so that team 1 (which wins every remaining gold) reaches the best possible final rank.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting, Math
Solved: No attempts yet

Problem

N teams participate in a programming olympiad. The teams are numbered from 1 to N.

The olympiad consists of multiple events. At the end of each event, the teams in first, second, and third place receive a gold, silver, and bronze medal, respectively. There are no ties within an event, and a team can receive at most one medal in a single event.

After all events are finished, the final ranking is decided in this order.

The team with more gold medals ranks higher.
If the gold medal counts are equal, the team with more silver medals ranks higher.
If the gold and silver medal counts are both equal, the team with more bronze medals ranks higher.
If all three medal counts are equal, the team with the smaller team number ranks higher.

There are still L events remaining, and the current medal counts of all teams are given. Suppose team 1 receives the gold medal in every remaining event. By distributing the remaining silver and bronze medals appropriately, find the lowest final rank that team 1 can have.

The highest rank is 1, the next highest rank is 2, and so on.

Input

The first line contains the number of teams N (3 <= N <= 50) and the number of remaining events L (0 <= L <= 10,000).

Each of the next N lines contains three integers: the current numbers of gold, silver, and bronze medals for one team, in order from team 1 to team N. Each medal count is a nonnegative integer not greater than 10,000.

The current totals of gold, silver, and bronze medals do not have to be equal. However, in each of the remaining L events, all three medals are awarded.

Output

Print the lowest final rank that team 1 can have.

Hint

If another team has far more gold medals than team 1 can reach, team 1 must rank below that team regardless of how the remaining medals are distributed. Among teams whose gold count can match team 1's final gold count, giving enough silver medals to two of them can make both rank above team 1, so team 1's final rank can drop to 4.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
3 1
0 0 0
1 0 0
1 0 0
```
Expected output
```
3
```
Example 3
Input
```
3 2
0 0 0
1 0 0
1 0 0
```
Expected output
```
1
```
Example 4
Input
```
3 6
0 7 6
6 0 0
6 1 1
```
Expected output
```
1
```
Example 5
Input
```
3 5
0 5 5
5 0 0
5 0 10
```
Expected output
```
2
```

Example 6

Input

Expected output