← 返回题目列表

Codeforces · 545/C

C. 樵夫

中文机器翻译题面 查看原题

小苏西每天睡前听童话故事。今天的童话故事是关于伐木工的,小女孩立刻开始想象砍柴工砍柴的情景。她想象了下面描述的情况。

沿路有 n 棵树,坐标为 x1、x2、...、xn。每棵树都有其高度 hi。樵夫可以砍倒一棵树并将其向左或向右砍倒。之后它占据段 [xi - hi, xi] 或 [xi;xi + hi] 之一。没有被砍倒的树占据一个坐标为 xi 的点。如果被倒下的树占据的部分不包含任何被占据的点,伐木者就可以砍倒一棵树。樵夫想要加工尽可能多的树木,因此苏西想知道最多可以砍伐多少棵树。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 树的数量。

接下来的 n 行包含整数对 xi, hi (1 ≤ xi, hi ≤ 109) — 第 і 棵树的坐标和高度。

这些对按 xi 升序给出。没有两棵树位于具有相同坐标的点。

输出

打印一个数字 — 根据给定规则您可以砍伐的最大树数。

示例

输入 #1

5
1 2
2 1
5 10
10 9
19 1

输出 #1

3

输入 #2

5
1 2
2 1
5 10
10 9
20 1

输出 #2

4

注意

在第一个示例中,您可以像这样砍伐树木:

- 将第一棵树倒在左侧 - 现在它占据段 [ - 1;1]
- 将第二棵树倒在右侧 - 现在它占据段 [2;3]
- 离开第三棵树 - 它占据点 5
- 离开第四棵树 - 它占据点 10
- 向右倒下第五棵树 - 现在它占据了段 [19;20]

在第二个示例中,您还可以将第 4 棵树砍倒到右侧,之后它将占据段 [10;19]。