Description

Xiaogang is playing a computer game provided by JSOI called "Emergency Building Repair": after an intense battle, the T tribe has eliminated all invaders from the Z tribe. However, $N$ buildings in the T tribe’s base have been severely damaged and will be completely destroyed if not repaired quickly. There is only one repair worker in the base. Although he can reach any building instantly, repairing each building takes a certain amount of time. The worker can repair only one building at a time and must finish repairing one building before starting the next. If a building is not fully repaired within a certain period of time, it will be scrapped. Your task is to help Xiaogang determine a repair order to repair as many buildings as possible.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain two integers $T_1, T_2$ describing a building: repairing this building takes $T_1$ seconds, and if the repair is not completed within $T_2$ seconds, the building will be scrapped.

Output Format

Output an integer $S$, the maximum number of buildings that can be repaired.

4
100 200
200 1300
1000 1250
2000 3200

3

Hint

Constraints: For $100 \%$ of the testdata, $1 \le N < 150000$, and $1 \le T_1 < T_2 < 2^{31}$.

Translated by ChatGPT 5