14587번 - 도미노 (Large)

문제

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

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

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500,000)

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

출력

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

제한

힌트