斯科特·朗 (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。