题目描述

有 $N$ 件事，其中第 $i$ 件事需要 $T_i$ 分钟完成。一个人从 $0$ 时刻开始工作，每分钟只能做一件事，且一件事做到一半的时候，不能停下换另一件事。

每件事都有一个过期时间。第 $i$ 件事的最晚启动时间为 $D_i$，其含义是，第 $i$ 件事必须在 $0$ 时刻后的 $D_i$ 分钟内启动，否则就过期了。

请问，如何才能让尽量多的事情按期完成，输出可以完成的最大值。

输入格式

• 第一行：单个整数表示 $N$
• 第二行到第 $N+1$ 行：每行两个整数表示 $D_i$ 与 $T_i$

输出格式

• 单个整数：表示答案。

2
5 10
6 9

1

样例解释 1

两件事只能做一件，开始任何一件都来不及做另一件事。

2
4 10
0 4

2

样例解释 2

先做第二件事，再做第一件事

数据范围

• $30\%$ 的数据，$1\leq N\leq 20$，$0\leq D_i\leq 100$，$1\leq T_i\leq 100$
• $50\%$ 的数据，$1\leq N\leq 1000$
• $100\%$ 的数据，$1\leq N\leq 300,000$，$0\leq D_i\leq 10^{18}$， $1\leq T_i\leq 10^{18}$

来源

改编自 USACO 2024 Dec Gold Job Completion