3827: 课程表安排

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:13 解决:4

题目描述

学校开设了 N 门课程,每门课程有两个属性:duration(课程持续时间,单位:天)和 lastDay(课程截止时间,单位:天)。你需要安排这些课程的学习计划,规则如下: 每天只能学习一门课程,且一门课程必须连续学习完(例如:一门持续 3 天的课程,需要占用 3 个连续的整天)。 一门课程必须在其截止时间(含)之前完成学习(例如:截止时间为 5 天的课程,最晚第 5 天结束学习)。 你可以按任意顺序选择课程学习,但不能同时学习多门课程。 请你计算:最多可以完成多少门课程的学习。

输入

第一行输入一个整数 N(1 ≤ N ≤ 10000),表示课程的数量。接下来 N 行,每行输入两个整数 duration 和 lastDay(1 ≤ duration ≤ lastDay ≤ 10000),分别表示一门课程的持续时间和截止时间。

输出

输出一个整数,表示最多可以完成的课程数量。

样例输入 复制

4
100 200
200 1300
1000 1250
2000 3200

样例输出 复制

3