#P18960. [SEUSA2026] I. 蛋白奶昔争夺战(Protein Shake Prognosis)

[SEUSA2026] I. 蛋白奶昔争夺战(Protein Shake Prognosis)

蛋白奶昔争夺战(Protein Shake Prognosis)

题目描述

房间内有 nn 名竞争者。每人有一个力量值,以及若干瓶蛋白奶昔。你也有自己的力量值和奶昔。

你可以逐次执行任意多次以下操作:

  • 喝掉自己的一瓶奶昔,使自己的力量值增加 11。只有拥有奶昔时才能执行。
  • 驱逐一名力量值严格小于你的竞争者,并取走他当前剩余的全部奶昔。被驱逐者立即离开房间。

你每执行一次操作后,所有仍留在房间内、且还有奶昔的竞争者都会各喝一瓶奶昔,使各自力量值增加 11,奶昔数量减少 11。已经离开房间者不再行动。

若选择最优的操作顺序,你最多能驱逐多少人?

输入格式

第一行三个整数 n,bu,pun,b_u,p_u,分别是竞争者数量、你的初始力量值和初始奶昔数。

随后 nn 行,每行两个整数 b,pb,p,表示一名竞争者的初始力量值和初始奶昔数。

数据范围为 1≤n≤2×1051\le n\le2\times10^5,0≤bu,pu,b,p≤10120\le b_u,p_u,b,p\le10^{12}。

输出格式

输出一个整数,表示最多能驱逐的人数。

样例

3 4 3
3 3
6 2
10 3
2

可以先驱逐第一人并拿到他的 33 瓶奶昔,然后喝光自己拥有的奶昔,最后驱逐第二人;无法驱逐第三人。

来源

2026 ICPC Southeast USA Regional Programming Contest Division 1,题目 I。

官方资料页 · 原题。中文根据用户提供的官方题面重新整理;全部测试数据来自赛事官方公开的数据包。