You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

目描述】

暑假到来，你得到一个新的游戏机，其中有这样一个游戏：

游戏地图可以看成一个二维的网格图，上下是两段障碍物。在游戏的一开始，玩家位于地图最左边的下边界上，且重力方向向下。

在每个时刻，你可以用手指点击屏幕，翻转重力的方向，或者往左或往右移动。

每次翻转重力方向时，你需要消耗的能量值等于上下底边之间的高度差。在左右移动的时候，玩家可以下降到对应重力方向更低的位置，但不能往上爬。当然，你也不能穿墙而过。在重力翻转的过程中，直到碰到地面之前，你都不能左右移动。

终点位于地图的最右端的下底边上，请计算为了到达终点，需要消耗能量的最小值。

【输入格式】

第一行包含一个正整数n，即地图的宽度。

第二行包含n个正整数，表示从左到右每个横坐标对应的上边界的高度。

第三行包含n个正整数，表示从左到右每个横坐标对应的下边界的高度。

【输出格式】

一行，一个整数，表示需要消耗能量的最小值，若无法到达终点则输出“-1”（不含引号）。

【样例输入1】

4

3 4 3 2

1 2 1 1

【样例输出1】

4

【数据范围】

对于40%的数据，1≤n≤15；

对于60%的数据，1≤n≤1,000；

对于100%的数据：1≤n≤100,000，1≤边界高度≤10^9^，保证同一横坐标的下边界高度小于上边界高度。