← 返回题目列表

Codeforces · 704/B

B. 蚁人

中文机器翻译题面 查看原题

斯科特·朗 (Scott Lang) 与达伦·克罗斯 (Darren Cross) 交战。他们所在的大厅里有n把椅子,从左到右编号为1,2,…,n。第 i 张椅子位于坐标 xi 处。 Scott 坐在 s 号椅子上,Cross 坐在 e 号椅子上。斯科特可以跳到所有其他椅子上(不仅仅是相邻的椅子)。他想从自己的位置(编号 s 的椅子)开始,精确地访问每把椅子一次,最后与 Cross 一起坐在编号 e 的椅子上。

众所周知,斯科特可以缩小或变大(只能变大到正常大小),因此在任何时刻他都可以变小或变大(正常)。问题是,他只能在椅子上缩小或变大(而不能在跳到另一张椅子上时在空中)。跳跃需要时间,但缩小和变大不需要时间。从 i 号椅子跳到 j 号椅子需要 |xi - xj|秒。此外,从椅子上跳下来并落在椅子上需要额外的时间。

如果斯科特想跳到左边的椅子上,他只能很小,如果他想跳到右边的椅子上,他应该很大。

从第 i 张椅子上跳下来需要:

- 如果他很小,则 ci 额外秒数。
- 否则会额外几秒(他很大)。

另外,落在第 i 张椅子上需要:

- 如果他很小,则额外几秒。
- 否则人工智能会额外秒(他很大)。

简单来说,从第 i 张椅子跳到第 j 张椅子需要:

- |xi - xj| 如果 j < i,则 + ci + bj 秒。
- |xi - xj| 否则+ di + aj秒(j > i)。

给定 x、a、b、c、d 的值,找到 Scott 到达 Cross 的最短时间,假设他想访问每把椅子一次。

输入

输入的第一行包含三个整数 n、s 和 e (2 ≤ n ≤ 5000, 1 ≤ s, e ≤ n, s ≠ e)——Scott 的椅子总数、起始位置和结束位置。

第二行包含 n 个整数 x1, x2, ..., xn (1 ≤ x1 < x2 < ... < xn ≤ 109)。

第三行包含 n 个整数 a1, a2, ..., an (1 ≤ a1, a2, ..., an ≤ 109)。

第四行包含 n 个整数 b1, b2, ..., bn (1 ≤ b1, b2, ..., bn ≤ 109)。

第五行包含 n 个整数 c1, c2, ..., cn (1 ≤ c1, c2, ..., cn ≤ 109)。

第六行包含 n 个整数 d1, d2, ..., dn (1 ≤ d1, d2, ..., dn ≤ 109)。

输出

打印斯科特到达十字架所需的最短时间,同时访问每把椅子一次。

示例

输入 #1

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

输出 #1

139

注意

在示例测试用例中,最佳解决方案为 $$4 \rightarrow 2 \rightarrow 1 \rightarrow 6 \rightarrow 5 \rightarrow 7 \rightarrow 3$$。花费的时间为 17 + 24 + 23 + 20 + 33 + 22 = 139。