The Serial Killer kidnaps people. These people were given a box each. Each box has different sizes. You can say they were measured in and cm. The Serial Criminal is very demanding. He wants the victims to stack their boxes such that each box fits into another. Since the box may not necessarily fit into one another, the Serial Criminal wants the victims to maximise the number of boxes put in such a manner. However, as the Serial Killer takes out his gun, he declares that he will give the victims only a few minutes to figure out how, if not he will shoot a person in the crowd. The victims depend on you as you can devise a program to do this quickly.
Note that for one box to be fitted into another box, and of that box must be strictly smaller than the other box's and value.
Input Specification
Line 1:
Line 2 to : and for each box, separated with a space
Output Specification
Line 1: The maximum number of boxes fitted in this manner possible. Answers are guaranteed to be less than .
Constraints
Subtask 1 [5%]
Subtask 2 [10%]
Subtask 3 [20%]
Subtask 4 [25%]
Subtask 5 [40%]
Subtask 6 [0%]
Sample test cases.
Sample Input 1
4
2 3
3 4
4 5
2 2
Sample Output 1
3
Sample Input 2
10
9 6
8 3
7 1
7 6
2 10
2 1
1 8
10 4
5 3
8 7
Sample Output 2
4
Explanation for Sample Output 2
Boxes of , , , can be fitted.
Comments
Since the original data were formatted incorrectly, the test case was updated, and all submissions were rejudged.