Наконечник

시간 제한2초메모리 제한1024 MB

요약

n개의 쌍 (x_i, y_i)이 주어질 때, 선택한 임의의 두 쌍 i, j가 x_i - y_j = x_j - y_i를 만족하지 않도록 하는 가장 큰 부분집합의 크기를 구한다.

난이도: 보통10점 중 7점
유형: 해시맵, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

Размышляя о предстоящих сражениях, Логан пришел к выводу, что вероятность успеха могут здорово увеличить наконечники на лезвия. Поэтому он решил заказать целый набор.

Набор состоит из $n$ наконечников. Так как в мире нет ничего совершенного, каждый $i$ -ый наконечник характеризуется парой чисел ( $x\_i$ , $y\_i$ ) --- количество способностей, которые данный наконечник улучшает и ухудшает соответственно. Выяснив это, Логан пришел к выводу, что нужно выбрать только часть набора. Эта часть считается максимально эффективной, если для любых двух наконечников с номерами $i$ и $j$ ( $i \neq j$ ), выполняется неравенство $x\_i - y\_j \neq x\_j - y\_i$ .

Так Логану осталось ответить на последний вопрос перед боем, какое максимальное число наконечников может быть выбрано, чтобы полученный поднабор был максимально эффективным. За помощью он решил обратиться именно к вам.

입력

В первой строке входного файла задано натуральное число $n$ --- количество наконечников в изначальном наборе ( $1 \le n \le 10^5$ ).

Каждая $i$ -ая из следующих $n$ строк содержит пару чисел ( $x\_i, y\_i$ ) --- описание $i$ -го наконечника ( $1 \le x\_i, y\_i \le 10^9$ ).

출력

В единственной строке выходного файла выведите одно число --- ответ на задачу.

예제1

예제 1
입력
```
5
4 5
2 8
1 3
7 3
6 5
```
예상 출력
```
4
```