13032번 - PS 테러리스트

세계 최고의 PS(PROBABLY S**SUNGMAN)를 뽑는 대회예선에서 죽을 쑨 현정이는 분을 못참고 주최인 S모 회사에 테러를 하기로 했다. 회사 지하에 잠입한 현정이는 그 곳에 일렬로 N개의 폭탄을 설치했다. 각 폭탄은 왼쪽부터 오른쪽으로 1~N번째로 구분한다. i번째 폭탄은 x_i좌표에 위치하며, p_i만큼의 파괴력을 가지고 있다. 각 폭탄은 바닥에 놓아진 순간부터 일정 시간이 흐르면 폭발하는 시한폭탄이다. 맞춰져있는 시간은 모두 같지만, 현정이가 폭탄을 오른쪽에서부터 놓았기 때문에 오른쪽에 있을 수록 폭발하는 시간이 조금씩 빠르다.

테러 꿈나무인 현정이는 폭탄의 폭발 범위가 겹쳐도 알아서 연쇄 폭발할거라 생각했지만, 이 폭탄들은 조금 특별하다. i번째 폭탄은 자신으로부터 왼쪽으로 p_i이내에 있는 모든 것을 파괴한다. 문제는 그 모든 것에 아직 폭발하지 않은 폭탄들도 포함된다는 것이다. 먼저 폭발한 폭탄으로 인해 파괴된 폭탄은 폭발하지 못하고 불발 폭탄이 된다.

당황한 현정이는 전설적인 테러리스트 성관이에게 도움을 청했다. 성관이는 이미 폭탄을 다시 배치하기에는 너무 늦었으므로, N번 폭탄보다 오른쪽에 즉석폭탄을 터뜨려 기존에 설치된 폭탄 중 몇개를 미리 불발폭탄으로 만드는 방법을 추천했다. 즉석폭탄은 x_n보다 큰 임의의 좌표 어디든, 현정이가 원하는 만큼의 파괴력으로 설치할 수 있다. 즉석폭탄은 어떤 폭탄보다도 먼저 폭발한다. 즉석폭탄을 설치했을 때, 최소로할 수 있는 불발폭탄의 개수는 몇 개일까?

한 줄에 현정이가 기존에 설치한 시한폭탄의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례대로 i번째 폭탄의 좌표 xi(0 ≤ xi ≤ 1,000,000)와 파괴력 p_i(1 ≤ p_i ≤ 1,000,000)가 주어진다. x_i가 작을수록 왼쪽, 클 수록 오른쪽에 있다. 서로 같은 위치에 존재하는 폭탄은 없다.

한 줄에 하나의 즉석폭탄을 추가해 최소로할 수 있는 불발 폭탄의 개수를 출력하라.

Sample1: 좌표 9에 파괴력이 2인 즉석폭탄을 설치하면 불발폭탄은 하나만 생긴다.

Sample2: 좌표 1337에 파괴력이 42인 즉석폭탄을 설치하면 불발폭탄은 세개만 생긴다.