You are given a set consisting of
disjoint segments of integers. That is,
can be represented as the union of
disjoint intervals of integers
. Let's call a set independent if it has the property that no element of the set is exactly
times another. Please find the size of the largest independent subset of
.
Input Specification
The first line will contain a single integer .
The next lines will each contain
integers
and
, representing that
contains all integers in the range
.
Output Specification
Output one integer, the size of the largest independent subset of .
Constraints
For all pairs such that
, either
or
.
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [40%]
No additional constraints.
Sample Input
3
5 7
9 11
1 3
Sample Output
6
Explanation
In this case, .
One of the largest independent subsets of is
.
Comments