题目描述

斯科特·朗正在与达伦·克罗斯作战。他们所在的大厅里有 $n$ 把椅子，从左到右编号为 $1,2,...,n$。第 $i$ 把椅子位于坐标 $x_{i}$。斯科特在编号为 $s$ 的椅子上，克罗斯在编号为 $e$ 的椅子上。斯科特可以跳到任意其他椅子上（不只是相邻的椅子）。他想从自己的位置（编号为 $s$ 的椅子）出发，恰好访问每把椅子一次，并最终到达编号为 $e$ 的椅子，与克罗斯会合。

众所周知，斯科特可以缩小或变大（变大只会变回正常大小），因此在任意时刻他都可以处于小形态或大形态（正常形态）。问题在于，他只能在椅子上缩小或变大（不能在跳向另一把椅子的空中改变形态）。跳跃需要时间，但缩小和变大不需要时间。从编号为 $i$ 的椅子跳到编号为 $j$ 的椅子需要 $|x_{i}-x_{j}|$ 秒。此外，从椅子上起跳和落到椅子上都需要额外时间。

如果斯科特想跳到左边的椅子，他只能处于小形态；如果他想跳到右边的椅子，他应该处于大形态。

从第 $i$ 把椅子起跳需要：

• 若他处于小形态，则额外需要 $c_{i}$ 秒。
• 否则（他处于大形态），额外需要 $d_{i}$ 秒。

同样，落到第 $i$ 把椅子上需要：

• 若他处于小形态，则额外需要 $b_{i}$ 秒。
• 否则（他处于大形态），额外需要 $a_{i}$ 秒。

更简单地说，从第 $i$ 把椅子跳到第 $j$ 把椅子恰好需要：

• 若 $j<i$，则需要 $|x_{i}-x_{j}|+c_{i}+b_{j}$ 秒。
• 否则（ $j>i$ ），则需要 $|x_{i}-x_{j}|+d_{i}+a_{j}$ 秒。

给定 $x$、$a$、$b$、$c$、$d$ 的值，求斯科特在恰好访问每把椅子一次的前提下到达克罗斯所需的最短时间。

输入格式

输入的第一行包含三个整数 $n,s$ 和 $e$（ $2 \le n \le 5000$，$1 \le s,e \le n$，$s≠e$ ）——椅子的总数，以及斯科特的起始位置和终止位置。

第二行包含 $n$ 个整数 $x_{1},x_{2},...,x_{n}$（ $1 \le x_{1} < x_{2} < ... < x_{n} \le 10^{9}$ ）。

第三行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（ $1 \le a_{1},a_{2},...,a_{n} \le 10^{9}$ ）。

第四行包含 $n$ 个整数 $b_{1},b_{2},...,b_{n}$（ $1 \le b_{1},b_{2},...,b_{n} \le 10^{9}$ ）。

第五行包含 $n$ 个整数 $c_{1},c_{2},...,c_{n}$（ $1 \le c_{1},c_{2},...,c_{n} \le 10^{9}$ ）。

第六行包含 $n$ 个整数 $d_{1},d_{2},...,d_{n}$（ $1 \le d_{1},d_{2},...,d_{n} \le 10^{9}$ ）。

输出格式

输出斯科特在恰好访问每把椅子一次的情况下到达克罗斯所需的最短时间。

7 4 3
8 11 12 16 17 18 20
17 16 20 2 20 5 13
17 8 8 16 12 15 13
12 4 16 4 15 7 6
8 14 2 11 17 12 8

139

提示

在样例测试中，一个最优方案为 $4\to2\to1\to6\to5\to7\to3$。花费的时间为 $17+24+23+20+33+22=139$。