完成课程的最大数量

题目描述

你准备学习 (n) 门不同的在线课程，课程编号为 $(1\sim n)$。

第 (i) 门课程具有两个属性：

• 学习该课程需要连续花费 $(t_i)$ 天；
• 该课程必须在第 $(d_i)$天或之前完成。

你从第 (1) 天开始学习。

在同一时间内，你最多只能学习一门课程。一旦开始学习某门课程，就必须连续学习$(t_i)$ 天，中途不能暂停或学习其他课程。

你可以自由选择课程的学习顺序，也可以放弃其中的一些课程。

请计算你最多能够完成多少门课程。

---

输入格式

第一行输入一个整数 (n)，表示课程数量。

接下来 (n) 行，每行输入两个整数 $(t_i,d_i)$，分别表示第 (i) 门课程的学习时长和最晚完成日期。

---

输出格式

输出一个整数，表示最多能够完成的课程数量。

---

样例 1

输入

4
100 200
200 1300
1000 1250
2000 3200

输出

3

样例解释

共有 (4) 门课程，最多可以完成其中 (3) 门。

一种可行的学习顺序为：

1. 学习第 (1) 门课程，需要 (100) 天，在第 (100) 天完成；
2. 学习第 (3) 门课程，需要 (1000) 天，在第 (1100) 天完成；
3. 学习第 (2) 门课程，需要 (200) 天，在第 (1300) 天完成。

这三门课程都在各自的截止日期之前完成。

如果继续学习第 (4) 门课程，则会在第 (3300) 天完成，超过它的截止日期 (3200)，因此无法再完成第 (4) 门课程。

所以最多能够完成 (3) 门课程。

---

样例 2

输入

1
1 2

输出

1

样例解释

唯一的一门课程需要学习 (1) 天，截止日期为第 (2) 天，因此可以完成。

---

样例 3

输入

2
3 2
4 3

输出

0

样例解释

第 (1) 门课程需要 (3) 天，但必须在第 (2) 天或之前完成，因此无法完成。

第 (2) 门课程需要 (4) 天，但必须在第 (3) 天或之前完成，因此也无法完成。

所以最多能完成 (0) 门课程。

---

数据范围

1 ≤ n ≤ 10000
1 ≤ ti ≤ 10000
1 ≤ di ≤ 10000

---

补充说明

如果当前已经学习了若干门课程，总学习时间为 (S)，接下来学习第 (i) 门课程后，完成时间为：

S + ti

只有满足：

S + ti ≤ di

这门课程才能在截止日期之前完成。

课程的输入顺序不代表实际学习顺序，你可以重新安排课程的学习顺序。