Blade Tips

Interview

Time limit2sMemory limit1024 MB

Summary

Given n tips with values x and y, find the largest subset where every x+y sum is distinct, which is the count of distinct sums.

Level: Easy3 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

Before the battle, Logan concluded that blade tips could greatly raise his chances of winning, so he decided to order a full set.

The set has $n$ tips. Nothing in the world is perfect, so each $i$ -th tip is described by a pair $(x_i, y_i)$ : the number of abilities it improves and the number it worsens, respectively. Logan decided to choose only part of the set. A subset is called maximally effective if for any two tips $i$ and $j$ ( $i \neq j$ ), the inequality $x_i - y_j \neq x_j - y_i$ holds.

What is the maximum number of tips that can be chosen so that the subset is maximally effective?

Input

The first line contains a natural number $n$ , the number of tips in the original set ( $1 \le n \le 10^5$ ).

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ , describing the $i$ -th tip ( $1 \le x_i, y_i \le 10^9$ ).

Output

Print one number, the answer to the problem.

Examples1

Example 1
Input
```
5
4 5
2 8
1 3
7 3
6 5
```
Expected output
```
4
```