Olympic Country Ranking

Interview

Time limit1sMemory limit128 MB

Summary

Count how many countries beat country K on gold, then silver, then bronze medals, and report its rank.

Level: Easy2 of 10
Topics: Sorting, Array
Solved: No attempts yet

Problem

At the Olympics the point is to take part, so no official ranking of countries is kept. Still, many people care how their own country does, so an unofficial ranking is common. Given the number of gold, silver, and bronze medals each country won, the usual rule for deciding which country did better is:

The country with more gold medals ranks higher.
If the gold counts are equal, the country with more silver medals ranks higher.
If both gold and silver counts are equal, the country with more bronze medals ranks higher.

Each country is identified by an integer from 1 to $N$ . A country's rank is defined as (the number of countries that did strictly better than it) $+ 1$ . Two countries with identical gold, silver, and bronze counts share the same rank. For example, if country 1 won 1 gold and 1 silver, countries 2 and 3 each won 1 silver, and country 4 won no medals, then country 1 is 1st, countries 2 and 3 tie for 2nd, and country 4 is 4th. In this case there is no 3rd place.

Given each country's gold, silver, and bronze medal counts, write a program that reports the rank of a given country.

Input

The first line contains the number of countries $N$ ( $1 \le N \le 1{,}000$ ) and the country number $K$ ( $1 \le K \le N$ ) whose rank you want, separated by a space. Each country is identified by an integer from 1 to $N$ . Each of the next $N$ lines contains a country's number followed by the gold, silver, and bronze medal counts it won, separated by spaces. The countries are not necessarily listed in numeric order. The total number of medals is at most $1{,}000{,}000$ .

Output

Print a single integer on one line: the rank of country $K$ . The rank must follow the rule defined above.

Examples2

Example 1
Input
```
4 3
1 1 2 0
2 0 1 0
3 0 1 0
4 0 0 1
```
Expected output
```
2
```
Example 2
Input
```
4 2
1 3 0 0
3 0 0 2
4 0 2 0
2 0 2 0
```
Expected output
```
2
```