#1547. [GESP202509 七级] 金币收集
[GESP202509 七级] 金币收集
说明
小 A 正在游玩收集金币的游戏。具体来说,在数轴上将会出现 $n$ 枚金币,其中第 $i$ 枚($1\le i\le n$)金币将会在时刻 $t_i$ 出现在数轴上坐标为 $x_i$ 的位置。小 A 必须在时刻 $t_i$ 恰好位于坐标 $x_i$,才可以获得第 $i$ 枚金币。
游戏开始时为时刻 $0$,此时小 A 的坐标为 $0$。正常来说,小 A 可以按游戏机的按键在数轴上左右移动,但不幸的是游戏机的左方向键失灵了。小 A 每个时刻只能选择保持不动,或是向右移动一个单位。换言之,如果小 A 在时刻 $t$ 的坐标为 $x$,那么他在时刻 $t+1$ 的坐标只能是 $x$ 或是 $x+1$ 二者之一,分别对应保持不动和向右移动。
小 A 想知道他最多能收集多少枚金币。你能帮他收集最多的金币吗?
输入格式
第一行,一个正整数 $n$,表示金币的数量。
接下来 $n$ 行,每行两个正整数 $x_i,t_i$,分别表示金币出现的坐标与时刻。
输出格式
输出一行,一个整数,表示小 A 最多能收集的金币数量。样例
3
1 6
3 7
2 42
提示
输入样例2:
4 1 1 2 2 1 3 2 4
样例2输出:
3
对于 $40\%$ 的测试点,保证 $1\le n\le 8$。
对于另外 $30\%$ 的测试点,保证 $1\le n\le 100$,$1\le x_i\le 100$,$1\le t_i\le 100$。
对于所有测试点,保证 $1\le n\le 10^5$,$1\le x_i\le 10^9$,$1\le t_i\le 10^9$。