题目描述

ncez中学请来北斗学友的史老师团队（孙老师、尹老师、徐老师）进行为期8天的冬令营集训，到达学校之后，史老师首先要前往会议室参加开营仪式。会议室建在了学校最高级的楼：信息楼。信息楼从 $1$ 层到 $N$ 层共 $N$ 层楼，会议室也是建在了风景最为开阔的顶层 $N$ 层。

信息楼另一点特殊之处就在于，为了加快运行速度，电梯只有四个按钮：打开，关闭，向上，向下。并且 $i$ 层会有两个数值 $a_i,b_i$ 表示从 $i$ 层按向上按钮会向上走 $a_i$ 层楼，按向下按钮会向下走 $b_i$ 层楼，由于设计缺陷，电梯会出现目标楼层不存在的情况，此时对应按钮（向上或者向下）就会失效，也就是不能够走到不存在的楼层。

现在史老师从 $1$ 层进入信息楼，他在电梯里想要尽快到达 $N$ 层以参加开营仪式并开始指导团队的工作和学生们的学习，于是他命令尹老师帮他找出最少需要按几次按钮便可以从 $1$ 层到达 $N$ 层。

输入格式

第一行一个整数 $N$ ，表示共 $N$ 层楼，要从 $1$ 层坐电梯到 $N$ 层。

第二行 $N$ 个整数 $a_i$，表示从 $i$ 层按向上按钮会向上走 $a_i$ 层楼。

第三行 $N$ 个整数 $b_i$，表示从 $i$ 层按向下按钮会向下走 $b_i$ 层楼。

输出格式

一个整数表示最少按键次数，若无法到达则输出 -1 。

输入样例

10
4 6 5 7 5 4 2 2 2 1 
1 2 3 4 2 3 3 6 3 6 

输出样例

2

数据范围

对于前 $40\%$ 的数据，$1≤N≤10$ 。

对于前 $60\%$ 的数据，$1≤N≤1000$ 。

对于前 $100\%$ 的数据，$1≤N≤100000$ 。