‹ 上一题下一题 ›

j01293. 最少迟到任务未做

1000 ms 256 MB 测试点 20 通过率 33% J-29·贪心 J·算法自拟题贪心

文件读写输入j01293.in输出j01293.out

题目描述

单台机器从 $0$ 时刻开始串行加工任务，任务 $i$ 需要连续加工 $p_{i}$ 时间，截止时间为 $d_{i}$ （完成时刻 $\leq d_{i}$ 即为按时）。你可以放弃任意一些任务，被放弃的任务不占用机器时间。求最多有多少个任务能按时完成。

输入格式

第一行一个正整数 $n$ ；接下来 $n$ 行每行两个整数 $p_{i}, d_{i}$ 。

输出格式

一行一个整数，即最多按时完成的任务数。

样例

输入

输出

数据范围

$1 \leq n \leq 2 \times 1 0^{5}$ ， $1 \leq p_{i}, d_{i} \leq 1 0^{9}$ （请用 long long）

输入

输出

答案