Hide

Problem E
I Wanna Be The Very Best

In order to become the very best Pokenom trainer, Bash needs to prepare a team of Pokenom to participate in the Pokenom world championship.

Bash has $N$ Pokenoms. Each Pokenom has $3$ stats: Attack, Defense and Health. Bash wants to select $K$ Pokenoms with highest attack, $K$ Pokenoms with highest defense and $K$ Pokenoms with highest Health.

After selection, Bash found something strange: his team have less than $3 \times K$ Pokenoms!

Bash looks carefully at $N = 4$ Pokenoms he has:

  • ‘Chikapu’: Attack = $100$, Defense = $100$, Health = $100$

  • ‘Batterfly’: Attack = $10$, Defense = $10$, Health = $10$

  • ‘Mewthree’: Attack = $200$, Defense = $200$, Health = $80$

  • ‘Dragonon’: Attack = $150$, Defense = $150$, Health = $90$

When Bash selects Pokenom with $K = 1$, only ‘Mewthree’ and ‘Chikapu’ are selected! This is because ‘Mewthree’ has highest attack and highest defense!

Your task is simple, you are given the stats of all $N$ Pokenoms and the number $K$. Calculate how many different Pokenoms are there in Bash’s team.

Input

  • The first line of input contains $2$ integers $N$ and $K$ $(1 \le K \le N \le 1\, 000)$.

  • In the next $N$ lines, the $i$-th line contains $3$ integers: $A_ i$, $D_ i$ and $H_ i$, representing the $3$ stats of the $i$-th Pokenom. $A_ i$, $D_ i$ and $H_ i$ are unsigned $32$-bit integers.

It is guaranteed that no $2$ Pokenom have same Attack, no $2$ Pokenom have same Defense, and no $2$ Pokenoms have same Health.

Output

Output one line containing exactly one integer: the number of Pokenom in Bash’s team.

Sample Input 1 Sample Output 1
4 1
100 100 100
10 10 10
200 200 80
150 150 90
2

Please log in to submit a solution to this problem

Log in