날끝
면접 대비시간 제한2초메모리 제한1024 MB
각 팁의 x_i + y_i 값이 서로 다르도록 고를 수 있는 최대 개수를 구합니다.
문제
로건은 다가오는 전투를 생각하다가 날끝을 달면 승률을 크게 높일 수 있다고 판단했다. 그래서 날끝 세트를 통째로 주문하기로 했다.
세트는 개의 날끝으로 구성된다. 완벽한 물건은 없어서, 번째 날끝은 두 정수의 쌍 로 표현된다. 는 강화하는 능력의 개수이고, 는 약화하는 능력의 개수이다. 로건은 세트의 일부만 고르기로 했다. 선택한 부분 집합에서 서로 다른 두 날끝 , ()에 대해 항상 가 성립하면, 그 부분 집합을 최대로 효율적이라고 한다.
로건이 전투 직전에 알고 싶은 것은, 최대로 효율적인 부분 집합으로 고를 수 있는 날끝의 최대 개수이다.
입력
첫 줄에 원래 세트에 있는 날끝의 개수인 자연수 이 주어진다 ().
다음 개의 줄에는 각각 번째 날끝을 나타내는 두 정수 , 가 주어진다 ().
출력
답을 한 줄에 출력한다.