跳房子

题目描述

跳房子游戏是西西艾弗岛上孩子们的传统娱乐方式。今天小 P 造访了西西艾弗岛， 小 C 向他示范了跳房子游戏该怎么玩。

在地面上有一字排开的 $n$ 个格子，每个格子上都写着一个数字，第 $i$ 个格子上写着的数字是 $a_i$。这些数字满足 $a_i < i$ 且 $a_n = 0$。

一开始，小 C 站在第一个格子上。小 C 是一个擅长跳跃的人，他可以往前跳很远，但为了游戏的趣味性，小 C 规定在第 $i$ 个格子上最多能往前跳 $k_i$ 格，而且不能跳到第 $n$ 个格子后面。也就是说，如果小 C 现在站在第 $i$ 个格子上，那么他可以跳到第 $i + 1$ 个格子和第 $min(n, i + k_i)$ 个格子之间的任意格子上。

根据跳房子游戏的规则，如果小 C 在一次跳跃之后落到了第 $i$ 个格子上，那么他需要后退 $a_i$ 格，也就是说小C 在跳跃后会站在第 $i - a_i$ 个格子上。玩了一会之后，小 P 突然好奇，小 C 最少需要跳多少次才能到达第 $n$ 个格子呢？

小 C 也不知道这个答案，于是他只能来请教你。

输入格式

第一行一个正整数 $n$，代表格子的数量。 第二行n 个非负整数 $a_1, a_2, . . . , a_n$，其中 $a_i$ 表示第 $i$ 个格子上的数字。 第三行n 个非负整数 $k_1, k_2, . . . , k_n$，其中 $k_i$ 表示小 C 在第 $i$ 个格子时能往前跳的最大格数。

数据范围

对于 $30\%$ 的数据， $n \le 1000$ 对于另外 $30\%$ 的数据，$k_i \le k_{i + 1}$ 对于所有测试数据，$n \le 10^5，0 \le a_i < i，1 \le k_i \le 10^9$

输出格式

输出一行一个整数表示小 C 到达第 $n$ 个格子需要的最少跳跃次数，如果小 C 不能到达第 $n$ 个格子输出 ‐1。

样例 #1

样例输入 #1

10
0 1 1 1 1 3 1 0 3 0
2 4 5 4 1 4 1 3 5 3

样例输出 #1

4

提示

样例解释1

从第 $1$ 个格子出发，首先往前跳 $2$ 格到第 $3$ 个格子，然后后退一格，停在第 $2$ 个格子。 从第 $2$ 个格子往前跳 $3$ 个格子到第 $5$ 个格子，后退一格，停在第 $4$ 个格子。 从第 $4$ 个格子往前跳 $4$ 个格子到第 $8$ 个格子，不需要后退，停在第 $8$ 个格子。 从第 $8$ 个格子往前跳两格即到达第 $10$ 个格子。总共跳跃 $4$ 次。