Skip to content

11624: 【原1624】Balloons

题目

题目描述

author: Codeforces, Spy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1624

Description

模仿ACM比赛,某次机考中,你每AC一题就能得到一个气球。

每个人都想得到更多的气球,但是,如果你的气球数(提供的浮力)超过你的体重,那么,你就会飞起来。当然,飞走的同学机考成绩将被视为无效。

机考结束后,助教们会根据气球数进行排名,排名不计罚时,只与题数有关。因此,拥有相同气球个数的同学在榜上并列。

你很想得到更好的名次,但是偷偷拿走别人的气球是伤害同学感情的行为,于是你打算把自己的气球送给别人。

现在你想知道某次机考中你最好的名次会是多少。

Input Format

第一行有一个整数\(N\) ,代表有N个编号为\(1~N\)同学,你的编号为1。 接下来 \(N\) 行,每行两个整数 \(ac,w\)。表示该次机考结束时,编号为i的同学获得了\(ac\)个气球,体重为 \(w\)。(体重单位也以气球个数来衡量)

Output Format

输出一行代表你能得到的最好名次。

Sample Input

8
20 1000
32 37
40 1000
45 50
16 16
16 16
14 1000
2 1000

Sample Output

3

Sample Input

7
4 4
4 4
4 4
4 4
4 4
4 4
5 5

Sample Output

2

Note

在第一个栗子中,你最初有20个气球,名次为4。把其中6个给2号同学,再拿6个给5号同学,再各拿一个给6号、7号同学。最终你还有6个气球,但是由于2、5、6、7号同学都飞走啦,所以你最终名次为3。

Limits

对于\(100\%\)的数据,\(N\in [2,300000],ac \leq w \in [0,10^18]\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!