该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：2 Sec 内存限制：256 MB 输入文件：gabbage.in 输出文件：gabbage.out

公园里有 $n$ 个垃圾，计划由 $n$ 名社区志愿者负责回收这些垃圾。

• 志愿者 $i(0 \le i \lt n)$ 的初始位置为坐标 $(a_i,0)$；

• 垃圾 $j(0 \le j \lt n)$ 的初始位置为坐标 $(x_j,y_j)$。

初始状态下，志愿者与垃圾均沿 $x$ 轴方向按顺序排列，即满足 $a_0 \le a_1 \le \ldots \le a_{n-1}$，且 $x_0 \le x_1 \le \ldots \le x_{n-1}$。

志愿者 $i$ 若要回收“垃圾 $j$、垃圾 $j+1$、……、垃圾 $i$”（其中 $0 \le j \le i$）这一连续区间内的所有垃圾，所需“劳力”等于“垃圾 $j$ 与志愿者 $i$ 的曼哈顿距离”。

志愿者 $i$ 无法回收编号大于 $i$ 的垃圾；若志愿者 $i$ 不回收任何垃圾，其劳力为 $0$。

请设计回收方案，使回收所有垃圾的“总劳力”最小化。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$。

第三行 $n$ 个整数 $x_0,x_1,\ldots,x_{n-1}$。

第四行 $n$ 个整数 $y_0,y_1,\ldots,y_{n-1}$。

输出格式

一个整数，表示回收所有垃圾的“总劳力”最小值。

样例

样例 1

4
0 1 2 3
0 1 2 3
1 1 1 1

4

样例说明：让志愿者 $i$ 回收垃圾 $i$ 是最优方案。

由于每个垃圾对应的曼哈顿距离均为 $1$，将这些距离相加，总和为 $4$，因此答案是 $4$。

样例 2

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

13

样例说明：让志愿者 $3$ 回收所有垃圾是最优方案，志愿者 $0$、$1$、$2$ 则处于空闲状态，不回收任何垃圾。

由于志愿者 $3$ 要回收“垃圾 $0$ 到垃圾 $3$”这一区间的所有垃圾，因此需要付出的劳力等于“志愿者 $3$ 与垃圾 $0$ 的曼哈顿距离”。

已知志愿者 $3$ 的初始位置为 $(3, 0)$，垃圾 $0$ 的初始位置为 $(0, 10)$，二者的曼哈顿距离为 $|3 - 0| + |0 - 10| = 3 + 10 = 13$，因此答案为 $13$。

样例 3

4
0 1 2 3
0 1 2 3
2 2 2 2

5

样例说明：让志愿者 $3$ 回收所有垃圾是最优方案，志愿者 $0$、$1$、$2$ 则处于空闲状态，不回收任何垃圾。

由于志愿者 $3$ 要回收“垃圾 $0$ 到垃圾 $3$”这一区间的所有垃圾，因此需要付出的劳力等于“志愿者 $3$ 与垃圾 $0$ 的曼哈顿距离”。

已知志愿者 $3$ 的初始位置为 $(3, 0)$，垃圾 $0$ 的初始位置为 $(0, 2)$，二者的曼哈顿距离为 $|3 - 0| + |0 - 2| = 3 + 2 = 5$。

样例 4

10
3251 5690 6665 16359 20099 34165 44782 58006 70432 72049 
2772 9289 40088 44279 57294 57580 57685 61437 68039 73446 
64849 45751 58453 17408 55499 38832 58870 71951 66081 4577 

113920

数据范围

对于 12% 的数据，$n \le 10$。

对于 32% 的数据，$n \le 1000$。

对于 100% 的数据，$1 \le n \le 3 \times 10^5$，$0 \le a_i,x_i,y_i \le 10^5$，$a_0 \le a_1 \le \ldots \le a_{n-1}$，$x_0 \le x_1 \le \ldots \le x_{n-1}$。