2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30

Box packing

Zharaskhan is working hard in Facegle. But after we announced KBTU Open 2021 spring, he decided to come back to Almaty and help us in preparation. Traditionally, when people come abroad, they bring gifts. So Zharaskhan prepared n boxes, i-th one is of size ai * bi (the height doesn’t matter), to make n people happy.

It turns out, air transport regulations do not allow more that k boxes per person for the flight. What Zharaskhan came up with, is that he can put box into another boxes (items are then placed in the most deep box) if the sizes fit. For example, if there are 3 boxes 2 * 2, 2 * 4 and 5 * 5, he can put first one into the second, and then second (which already contain first box) inside the third one. For safety of the boxes, Zharaskhan cannot put two separate boxes within one box (but can put box containing box within another box that doesn’t contain box). Pretty much like russian doll Matryoshka.

Help Zharaskhan to make as many people happy as possible, knowing the air transport regulations.


At the first line there are two integers n and k (1n105, 1k100).

At the next n lines, i-th line contain two space separated integers ai and bi (1ai, bi109).


Output single integer - maximal number of boxes Zharaskhan can take with him, packing everything within not more than k boxes.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 1
2 2
4 2
3 4
5 5
Output example #1
Input example #2
4 2
2 2
4 2
3 4
5 5
Output example #2
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem D