## Maximum Independent Subset

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 1G

Author:
Problem types

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 .

#### Sample Input

3
5 7
9 11
1 3

#### Sample Output

6

#### Explanation

In this case, .

One of the largest independent subsets of is .