题目描述

直线上有 $n$ 个高地，第 $i$ 个位于 $x_i$ 处，高度为 $h_i$。位于 $x_i$ 的高地可覆盖所有满足 $|x_i-x_j|\le h_i$ 的高地 $j$。你需要选择一些高地派兵占领。若一个高地已经被任意已占领高地覆盖，则无需额外派兵。求最少占领数。

输入格式

第一行整数 $n$。第二行 $n$ 个整数 $x_1,\dots,x_n$（互不相同）。第三行 $n$ 个整数 $h_1,\dots,h_n$。

输出格式

一行一个整数。

3
1 3 5
2 1 2

2

4
5 10 15 20
6 6 6 6

2

样例解释

样例 $1$：占领 $(x=1,h=2)$ 覆盖 $[-1,3]$→$\{1,3\}$；占领 $(x=5,h=2)$ 覆盖 $[3,7]$→$\{5\}$。共 $2$。

样例 $2$：高度均为 $6$。$x=5$ 覆盖 $[-1,11]$→$\{5,10\}$；$x=15$ 覆盖 $[9,21]$→$\{15,20\}$。共 $2$。

数据范围与约定

下发样例

下发样例下载