CF704B.Ant Man

Scott Lang is at war with Darren Cross. There are n chairs in a hall where they are, numbered with 1, 2, ..., n from left to right. The i-th chair is located at coordinate x__i. Scott is on chair number s and Cross is on chair number e. Scott can jump to all other chairs (not only neighboring chairs). He wants to start at his position (chair number s), visit each chair exactly once and end up on chair number e with Cross.

As we all know, Scott can shrink or grow big (grow big only to his normal size), so at any moment of time he can be either small or large (normal). The thing is, he can only shrink or grow big while being on a chair (not in the air while jumping to another chair). Jumping takes time, but shrinking and growing big takes no time. Jumping from chair number i to chair number j takes |x__i - x__j| seconds. Also, jumping off a chair and landing on a chair takes extra amount of time.

If Scott wants to jump to a chair on his left, he can only be small, and if he wants to jump to a chair on his right he should be large.

Jumping off the i-th chair takes:

• c__i extra seconds if he's small.
• d__i extra seconds otherwise (he's large).

Also, landing on i-th chair takes:

• b__i extra seconds if he's small.
• a__i extra seconds otherwise (he's large).

In simpler words, jumping from i-th chair to j-th chair takes exactly:

• |x__i - x__j| + c__i + b__j seconds if j < i.
• |x__i - x__j| + d__i + a__j seconds otherwise (j > i).

Given values of x, a, b, c, d find the minimum time Scott can get to Cross, assuming he wants to visit each chair exactly once.

斯科特·朗正在与达伦·克罗斯交战。他们所在的厅堂中有 $ n $ 把椅子，从左到右依次编号为 $ 1, 2, \dots, n $。第 $ i $ 把椅子位于坐标 $ x_i $ 处。斯科特位于编号为 $ s $ 的椅子上，而克罗斯位于编号为 $ e $ 的椅子上。斯科特可以跳向其余任意椅子（不仅限于相邻椅子）。他希望从自己所在的位置（编号为 $ s $ 的椅子）出发，恰好访问每把椅子一次，最终落在编号为 $ e $ 的椅子上与克罗斯会合。

众所周知，斯科特可以缩小或变大（仅能变回正常大小），因此在任意时刻，他只能处于“小”或“大”（即正常尺寸）两种状态之一。关键在于：他只能在椅子上（而非空中跳跃过程中）进行缩小或变大操作。跳跃需要耗时，但缩小或变大本身不耗时。从编号为 $ i $ 的椅子跳到编号为 $ j $ 的椅子需耗时 $ |x_i - x_j| $ 秒。此外，起跳和落地各自还需额外耗时。

若斯科特想跳向左侧的椅子（即目标椅子编号 $ j < i $），他必须处于“小”状态；若想跳向右侧的椅子（即 $ j > i $），他必须处于“大”状态。

从第 $ 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 $，求斯科特在恰好访问每把椅子一次的前提下，抵达克罗斯所在椅子（编号 $ e $）所需的最少时间。

The first line of the input contains three integers n, s and e (2 ≤ n ≤ 5000, 1 ≤ s, e ≤ n, s ≠ e) — the total number of chairs, starting and ending positions of Scott.

The second line contains n integers _x_1, _x_2, ..., x__n (1 ≤ _x_1 < _x_2 < ... < x__n ≤ 109).

The third line contains n integers _a_1, _a_2, ..., a__n (1 ≤ _a_1, _a_2, ..., a__n ≤ 109).

The fourth line contains n integers _b_1, _b_2, ..., b__n (1 ≤ _b_1, _b_2, ..., b__n ≤ 109).

The fifth line contains n integers _c_1, _c_2, ..., c__n (1 ≤ _c_1, _c_2, ..., c__n ≤ 109).

The sixth line contains n integers _d_1, _d_2, ..., d__n (1 ≤ _d_1, _d_2, ..., d__n ≤ 109).

输入的第一行包含三个整数 $n$、$s$ 和 $e$（$2 \leq n \leq 5000$，$1 \leq s, e \leq n$，$s \neq e$）—— 分别表示椅子的总数、Scott 的起始位置和结束位置。

第二行包含 $n$ 个整数 $x_1, x_2, ..., x_n$（$1 \leq x_1 < x_2 < ... < x_n \leq 10^9$）。

第三行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_1, a_2, ..., a_n \leq 10^9$）。

第四行包含 $n$ 个整数 $b_1, b_2, ..., b_n$（$1 \leq b_1, b_2, ..., b_n \leq 10^9$）。

第五行包含 $n$ 个整数 $c_1, c_2, ..., c_n$（$1 \leq c_1, c_2, ..., c_n \leq 10^9$）。

第六行包含 $n$ 个整数 $d_1, d_2, ..., d_n$（$1 \leq d_1, d_2, ..., d_n \leq 10^9$）。

Print the minimum amount of time Scott needs to get to the Cross while visiting each chair exactly once.

输出 Scott 在恰好访问每把椅子一次的前提下，到达十字路口所需的最少时间。

In the sample testcase, an optimal solution would be . Spent time would be 17 + 24 + 23 + 20 + 33 + 22 = 139.

在样例测试用例中，一个最优解为 。所花费的时间为 $17 + 24 + 23 + 20 + 33 + 22 = 139$。