H. Iamb and Trochee
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

One autumn evening, Monocarp felt a slight melancholy and, on a whim, decided to compose some poetry. But, being a true mathematician, he decided to approach this task with complete precision and mathematical rigor.

Monocarp knows $$$n$$$ different words in total, and for each word he knows two parameters: the number of syllables in the word and the position of the stressed syllable.

Using the available words, Monocarp wants to build a rhythmic line: a sequence of words in which every $$$k$$$-th syllable is stressed, for some integer $$$k$$$. Formally, to determine whether a sequence of words is a rhythmic line, we do the following:

  1. first, number all syllables of all words consecutively from left to right, starting from $$$0$$$;
  2. then, if there exist two integers $$$r$$$ and $$$k$$$ ($$$0 \le r \lt k$$$) such that syllable $$$i$$$ is stressed if and only if $$$i \bmod k = r$$$, then the sequence is a rhythmic line. Otherwise, it is not.

For example, the line "Twinkle, Twinkle, Little Star" is rhythmic, while "Hello world" is not.

Monocarp can use each word any number of times, but he wants his rhytmic line to feature diverse vocabulary. Help Monocarp determine the maximum number of different words he can use in one rhythmic line.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 20\,000$$$) — the number of different words Monocarp knows.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$s_i$$$ and $$$p_i$$$ ($$$1 \le s_i \le 200$$$; $$$1 \le p_i \le s_i$$$) — the number of syllables in the $$$i$$$-th word and the position of the stressed syllable.

Note that all words in the input are considered pairwise distinct, even if their pairs $$$(s_i, p_i)$$$ coincide.

Output

Print one integer — the maximum possible number of different words that Monocarp can fit into one rhythmic line.

Examples
Input
4
1 1
2 2
2 1
2 2
Output
4
Input
5
4 3
2 2
4 3
4 3
5 1
Output
4
Note

In the first example, Monocarp can build the following sequence of words: $$$[3, 1, 2, 4]$$$, whose rhythmic line can be represented as follows: Oo|O|oO|oO.

In the second example, Monocarp can build the following sequence: $$$[1, 2, 3, 2, 4]$$$, whose rhythmic line looks like this: ooOo|oO|ooOo|oO|ooOo.