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.
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 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 |