eolymp
bolt
Try our new interface for solving problems
Problems

Box packing

Box packing

Time limit 1 second
Memory limit 128 MiB

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 a[i] * b[i] (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.

Input data

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

At the next n lines, i-th line contain two space separated integers a[i] and b[i] (1a[i], b[i]10^9).

Output data

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

Examples

Input example #1
4 1
2 2
4 2
3 4
5 5
Output example #1
3
Input example #2
4 2
2 2
4 2
3 4
5 5
Output example #2
4
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem D