페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5833
서브태스크

광고2 (Advertisement 2) 2초 1024MB

문제

마을에는 N 명의 주민이 있으며 1에서 N까지 번호가 매겨져 있다. 거주자 i (1 ≤ i ≤ N)는 좌표 X_i에 살고 있으며 그 영향력은 E_i이다.

같은 좌표에 여러 거주자가 살고 있는 경우도 있으며, 영향력이 높은 거주자 일수록 홍보 효과가 큰 반면, 책을 사는 데 신중하다.

정올씨는 정보 과학의 책을 출판했다. 많은 사람들이 책을 사게 하기 위해 몇몇 거주자에게 책을 무료로 기부하려고 한다.

주민 i (1≤i≤N)에게 책을 기부했을 경우, 주민 i는 정올씨의 책을 갖게 된다.

책을 받지 못한 거주자 중 다음 조건을 충족시키는 모든 거주자 j (1 ≤ j ≤ N)는 정올씨의 책을 구매한다.

  • 조건: 거주자 i와 거주자 j 사이의 직선 거리는 E_i-E_j 이하이다. 즉 | Xi - Xj | ≤ Ei - Ej이다.

마을의 모든 거주자에게 정올씨의 책이 읽혀지면 정보 올림픽의 지명도가 크게 향상된다.

마을의 모든 주민이 정올씨의 책을 읽게 하기 위해 최소한 몇 명에게 기부해야 하는지 알아내자.


입력

다음과 같은 형식으로 입력이 주어진다.

N

X_1 E_1

X_2 E_2

.

.

.

X_N E_N

[제한]

1 ≦ N ≦ 500 \,000

1 ≦ Xi ≦ 10^9 (1 ≦ i ≦ N)

1 ≦ Ei ≦ 10^9 (1 ≦ i ≦ N)

주어지는 값은 모두 정수이다.


출력

마을의 모든 주민이 정올씨의 책을 얻기 위해 최소한 몇 명에게 기부해야 하는지 출력한다.


부분문제

번호 점수 조건
#110점

E_1 = E_2 = · · · = E_N

#223점

N ≦ 16

#336점

N ≦ 1 000

#431점

추가 제한 없음


예제1

입력
4
42
23
34
65
출력
2

예를 들어 다음과 같이 기부하면 JOI 국가의 주민 모두가 정올씨의 책을 얻을 수 있다.

• 거주자 3에게 기부한다.

• | X_3 - X_1 | = 1, E_3 - E_1 = 2 이기에 주민 1은 정올씨의 책을 사서 얻는다.

• | X_3 - X_2 | = 1, E_3 - E_2 = 1 이기에 주민 2는 정올씨의 책을 사서 얻는다.

• | X_3 - X_4 | = 3, E_3 - E_4 = -1 이기에 거주자 4는 정올씨의 책을 사지 않는다.

따라서 주민 1, 2, 3이 정올씨의 책을 얻게된다.

• 거주자 4에게 기부한다.

JOI 국가의 모든 주민이 정올씨의 책을 얻는다.

2 명 미만에게 기부함으로서 JOI 국가의 모든 주민이 정올씨의 책을 얻을 수 없으므로 2를 출력한다.

이 입력 예제는 서브태스크 2, 3, 4의 제약 조건을 충족한다.


예제2

입력
3
710
1010
710
출력
2

이 입력 예제는 모든 서브태스크의 제약 조건을 충족한다.


예제3

입력
10
31447678204745778
430226982292647686
327782937367372305
843320852822224390
687565054738216211
970840050766211141
563662348742939240
103739645854320982
294864525601612333
375952316469655019
출력
5

이 입력 예제는 서브태스크 2, 3, 4의 제약 조건을 충족한다.


출처

JOI 2023

역링크