A67240 | ⾦币收集

试题名称：⾦币收集

时间限制： 1.0 s

内存限制：512.0 MB

3.2.1     题目描述

⼩ A 正在游玩收集⾦币的游戏 。具体来说 ，在数轴上将会出现 n 枚⾦币 ，其中第 i 枚（ 1 ≤ i ≤ 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 想知道他最多能收集多少枚⾦币 。你能帮他收集最多的⾦币吗？

3.2.2     输入格式

第一⾏ ，一个正整数 n ，表⽰⾦币的数量。

接下来 n ⾏ ，每⾏两个正整数 x_i , t_i ，分别表⽰⾦币出现的坐标与时刻。

3.2.3     输出格式

输出一⾏ ，一个整数 ，表⽰⼩ A 最多能收集的⾦币数量。

3.2.4     样例

3.2.4.1     输入样例 1

3

1 6

3 7

2 4

3.2.4.2

1  2

3.2.4.2 输出样例 1

2

输入样例 2

4

1  1

2  2

1  3

2  4

3.2.4.4     输出样例 2

3

3.2.5     数据范围

对于 40% 的测试点 ，保证 1 ≤ n ≤ 8。

对于另外 30% 的测试点 ，保证 1 ≤ n ≤ 100 ，1  ≤ x_i ≤ 100 ，1 ≤ t_i ≤ 100。 

对于所有测试点 ，保证 1  ≤ n ≤ 10⁵ ，1  ≤ x_i ≤ 10⁹ ，1 ≤ t_i  ≤ 10⁹ 。