时间限制： 0.5 秒

空间限制： 512 MB

题目描述

跳房子游戏是西西艾弗岛上孩子们的传统娱乐方式。今天小 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, \dots, a_n$，其中 $a_i$ 表示第 $i$ 个格子上的数字。

第三行 $n$ 个非负整数 $k_1, k_2, \dots, k_n$，其中 $k_i$ 表示小 C 在第 $i$ 个格子时能往前跳的最大格数。

输出格式

输出到标准输出。

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

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

4

样例 1 解释

从第 $1$ 个格子出发，首先往前跳 $2$ 格到第 $3$ 个格子，然后后退一格，停在第 $2$ 个格子。

从第 $2$ 个格子往前跳 $3$ 个格子到第 $5$ 个格子，后退一格，停在第 $4$ 个格子。

从第 $4$ 个格子往前跳 $4$ 个格子到第 $8$ 个格子，不需要后退，停在第 $8$ 个格子。

从第 $8$ 个格子往前跳两格即到达第 $10$ 个格子。总共跳跃 $4$ 次。

5
0 1 2 3 0
3 4 4 10 15

-1

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务一（$30$ 分）：保证 $n \le 1000$；
• 子任务二（$30$ 分）：保证 $\forall 1 \le i < j \le n$ 都有 $k_i \le k_j$；
• 子任务三（$40$ 分）：无特殊限制。

对于所有数据，保证 $1 \le n \le 10^5,~ 0 \le a_i < i,~ 1 \le k_i \le 10^9$。

提示

本题输入量较大，请采用效率较高的读入方式。