解题思路

本题是一个典型的动态规划问题。忍者的目标是从第一排或第二排的房间 1 出发，到达第一排或第二排的房间 n，要求最小化消耗的时间。根据题意，我们可以从每个房间选择不同的路径（在两个房间之间跳跃或在同一排内移动），每种路径都有不同的消耗时间。我们需要通过动态规划来计算从起点到终点的最短时间。

动态规划状态定义

我们可以定义动态规划的状态如下：

• dp1[i] 表示从第一排的房间 i 出发，到达第 i 个房间所需的最小时间。
• dp2[i] 表示从第二排的房间 i 出发，到达第 i 个房间所需的最小时间。

题目内容

忍者在练习飞檐走壁。现在有两排房子。从左往右排列各有 $n$ 间。如下图。在每个房间的房顶。他有 $6$ 个选择:

第一排：$1$ $2$ $3$ ... $n$

第二排：$1$ $2$ $3$ ... $n$

1:从第一排房间 $i$ 到第一排的房间 $i+1$ 。消耗时间为两个房间的高度差。

2:从第二排房间 $i$ 到第二排的房间 $i+1$ 。消耗时间为两个房间的高度差。

3:从第一排房间 $i$ 到第二排的房间 $i$ 。消耗时间为两个房间的高度差 $*$ $2$ 。

4:从第二排房间 $i$ 到第一排的房间 $i$ 。消耗时间为两个房间的高度差 $*$ $2$ 。

5:从第一排房间 $i$ 到第二排的房间 $i+1$ 。消耗时间为两个房间的高度差 $*$ $3$ 。

6:从第二排房间 $i$ 到第一排的房间 $i+1$ 。消耗时间为两个房间的高度差 $*$ $3$ 。

注意:高度差应该是两个房间的高度的差的绝对值。

他希望花费最少的时间从第一排或第二排的房间 $1$ 开始，到达第一排或者第二排的房间 $n$ 。

请你求一下需要花费最少的时间是多少。

输入描述

一行：$n$ (每排的房子数，$1＜＝n＜＝10^5$)

一行：$a[1],a[2],...,a[n](1＜＝a[i]＜＝10^9)$

一行：$b[1],b[2],...,b[n](1＜＝b[i]＜＝10^9)$

输出描述

一个整数。需要花费的最少的时间。

样例1

输入

5
1 10 20 30 40
2 5 20 50 31

输出

31