A67240. ⾦币收集
题目描述
试题名称：⾦币收集
时间限制： 1.0 s
内存限制：512.0 MB
3.2.1 题目描述
⼩ A 正在游玩收集⾦币的游戏 。具体来说 ，在数轴上将会出现 n 枚⾦币 ，其中第 i 枚（ 1 ≤ i ≤ n）⾦币将会在时刻 ti 出现在数轴上坐标为 xi 的位置 。⼩ A 必须在时刻 ti 恰好位于坐标 xi ，才可以获得第 i 枚⾦币。
游戏开始时为时刻 0 ，此时⼩ A 的坐标为 0 。正常来说 ，⼩ A 可以按游戏机的按键在数轴上左右移动 ，但不幸的是 游戏机的左⽅向键失灵了 。⼩ A 每个时刻只能选择保持不动 ，或是向右移动一个单位 。换⾔之 ，如果⼩ A 在时刻 t 的坐标为 x，那么他在时刻 t + 1 的坐标只能是 x或是 x+ 1 ⼆者之一 ，分别对应保持不动和向右移动。
⼩ A 想知道他最多能收集多少枚⾦币 。你能帮他收集最多的⾦币吗？
3.2.2 输入格式
第一⾏ ，一个正整数 n ，表⽰⾦币的数量。
接下来 n ⾏ ，每⾏两个正整数 xi , ti ，分别表⽰⾦币出现的坐标与时刻。
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 ≤ xi ≤ 100 ，1 ≤ ti ≤ 100。
对于所有测试点 ，保证 1 ≤ n ≤ 105 ，1 ≤ xi ≤ 109 ，1 ≤ ti ≤ 109 。