2018 ICPC Vietnam National Programming Contest

#### Start

2018-11-03 17:00 AKDT

## 2018 ICPC Vietnam National Programming Contest

#### End

2018-11-03 22:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -917 days 13:18:27

5:00:00

0:00:00

# Problem II 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