The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Final RoundFebruary 12, 2023 (Online)

2Advertisement 2

There are N residents in JOI Kingdom, numbered from 1 to N. Resident i (1 ≤ i ≤ N) lives at the coordinate
Xi on the real line, and its power of influence is Ei . It may be the case that more than one residents live at thesame coordinate. A resident with a large power of influence has a high advertising potential. But such a resident
is careful in buying books.
Rie published a book on informatics. In order to encourage many people to buy copies of the book, she candonate copies of the book to some residents. If she donates a copy of the book to Resident i (1 ≤ i ≤ N),Resident i will get a copy of Rie’s book. Moreover, among the residents who did not yet get copies of the book,every resident j (1 ≤ j ≤ N) satisfying the following condition will buy a copy of the book and get it.
The distance between Resident i and Resident j on the real line is less than or equal to Ei − E j . In otherwords, |Xi − X j | ≤ Ei − E j is satisfied.
If all the residents read Rie’s book, the Olympiads in Informatics will be greatly recognized. Write a program
which calculates the minimum number of residents who will be donated copies of Rie’s book so that all theresidents in JOI Kingdom will get copies of Rie’s book.

Input
Read the following data from the standard input.
N
X1 E1
X2 E2..
.
XN E N

OutputWrite one line to the standard output. The output should contain the minimum number of residents who willbe donated copies of Rie’s book.

Task 2- 1 / 3

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Final Round
February 12, 2023 (Online)

Constraints• 1 ≤ N ≤ 500 000.
• 1 ≤ Xi ≤ 109 (1 ≤ i ≤ N).
• 1 ≤ Ei ≤ 109 (1 ≤ i ≤ N).
• Given values are all integers.

Subtasks
1. (10 points) E1 = E2 = · · · = E N .
2. (23 points) N ≤ 16.
3. (36 points) N ≤ 1 000.
4. (31 points) No additional constraints.

Sample Input and Output
Sample Input 1Sample Output 1424 22 33 46 5For example, if Rie donates copies of the book in the following way, all the residents in JOI Kingdom will
get copies of Rie’s book.
• Rie donates a copy of the book to Resident 3.
• Since |X3 − X1 | = 1 and E3 − E1 = 2, Resident 1 will buy a copy of Rie’s book and get it.
• Since |X3 − X2 | = 1 and E3 − E2 = 1, Resident 2 will buy a copy of Rie’s book and get it.
• Since |X3 − X4 | = 3 and E3 − E4 = −1, Resident 4 will not buy a copy of Rie’s book.
Therefore, Residents 1, 2, 3 will get copies of Rie’s book.
• Rie donates a copy of the book to Resident 4. Since all the residents except Resident 4 already got copiesof Rie’s book, all the residents in JOI Kingdom finally get copies of Rie’s book.
Since it is impossible to donate copies of the book to less than two residents so that all the residents in JOI
Kingdom will get copies of Rie’s book, output 2.

Task 2- 2 / 3

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Final Round
February 12, 2023 (Online)

This sample input satisfies the constraints of Subtasks 2, 3, 4.
Sample Input 2

Sample Output 2

327 1010 107 10
This sample input satisfies the constraints of all the subtasks.
Sample Input 3

Sample Output 3

10531447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019
This sample input satisfies the constraints of Subtasks 2, 3, 4.

Task 2- 3 / 3