시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB87218213227.789%

문제

N개의 도미노가 일렬로 놓여있다. 각 도미노는 위치 Xi에서 높이 Hi로 세워져 있다. 같은 위치에 2개 이상의 도미노가 놓여있는 경우는 없다. 홍준이는 도미노를 밀어서 왼쪽 또는 오른쪽으로 넘어뜨릴 수 있다. 도미노가 넘어지는 동안 만나게 되는 모든 도미노들은 같은 방향으로 넘어진다.

높이가 h이고 위치 x에 있는 도미노를 왼쪽으로 넘어뜨린 경우를 생각해보자. (x-h)와 x 사이에 위치한 모든 도미노들은 왼쪽 방향으로 넘어진다. 마찬가지로 오른쪽으로 넘어뜨렸다면, x와 (x+h) 사이에 위치한 모든 도미노들이 오른쪽 방향으로 넘어질 것이다.

이제 홍준이는 최소 개수의 도미노만 넘어뜨려서 모든 도미노들을 넘어뜨리려고 한다. 홍준이를 도와 최소 몇 개의 도미노를 넘어뜨리면 되는지 그 개수를 계산하는 프로그램을 작성하여라.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 300)

둘째 줄부터 N개의 줄에는 각 도미노의 위치와 높이를 나타내는 2개의 정수 Xi와 Hi가 주어진다. (1 ≤ Xi, Hi ≤ 2,000,000,000)

출력

첫째 줄에 모든 도미노를 넘어뜨리기 위해서 최소 몇 개의 도미노를 넘어뜨려야 하는지 출력한다.

예제 입력 1

5
1 2
3 1
6 2
7 1
9 2

예제 출력 1

2

출처

University > 고려대학교 > 2017 고려대학교 프로그래밍 대회 > Div 1 D1번