橘子猫的DDL
题号:NC24229
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

众所周知,橘子猫正在工地搬砖。现在橘子猫的工头给了橘子猫n块砖,对于第i块砖需要在时间di之前搬到指定地点,同时搬运需要花费ti的时间。现在橘子猫想要在每块砖的DDL(deadline, 最后期限)之前搬尽可能多的砖。(任意一个时刻橘子猫只能搬一块砖,对于一块砖只需要要在DDL之前搬到指定地点,没有其他限制条件)。那么橘子猫最多能搬多少块砖?由于橘子猫忙于搬砖,需要你来帮他解决这个问题。

输入描述:

第一行一个n(1≤n≤106)。
接下来n行每行两个数分别表示di,ti。(0≤ti≤di≤108)。

输出描述:

一个数,表示最多能搬的砖数。
示例1

输入

复制
3
5 4
1 1
6 2

输出

复制
2