#5633. [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 4
2

提示

输入样例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$。

来源

GESP七级