B. Человек-муравей
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скотт Лэнг враждует с Дареном Кроссом. Они находятся в зале, где расположены n стульев, пронумерованных 1, 2, ..., n слева направо. Известно, что стул номер i расположен в точке с координатами xi. Скотт изначально сидит на стуле с номером s, а Кросс сидит на стуле с номером e. Скотт может с любого стула прыгнуть на любой другой (не обязательно соседний). Он хочет начать прыгать со стула номер s, посетить каждый стул ровно один раз и закончить на стуле с номером e, где сидит Кросс.

Как мы знаем, Скотт может сжаться или, наоборот, вырасти (вернуться к нормальному размеру), так что в каждый момент времени он будет либо маленьким, либо большим (нормальным). Изменять свой размер он может только сидя на стуле (но не в воздухе в процессе прыжка). Изменение размера происходит мгновенно, в то время как прыжок занимает определённое время. Прыжок со стула номер i на стул номер j занимает |xi - xj| секунд. Дополнительно некоторое время тратится на то, чтобы оттолкнуться от стула, и на приземление.

Чтобы прыгнуть на стул, расположенный левее, Скотту необходимо стать маленьким, а чтобы прыгнуть направо, требуется, наоборот, стать большим.

Прыжок с i-го стула занимает:

  • ci секунд, если Скотт маленький.
  • di секунд, если Скотт большой.

Приземление на i-й стул занимает:

  • bi секунд, если Скотт маленький.
  • ai секунд, если Скотт большой.

Другими словами, прыжок со стула i на стул j занимает:

  • |xi - xj| + ci + bj секунд, если j < i.
  • |xi - xj| + di + aj секунд, если j > i.

По данным значениям x, a, b, c, d найдите минимальное время, которое понадобится Скотту, чтобы добраться до Кросса, если он хочет посетить все стулья ровно по одному разу.

Входные данные

В первой строке входных данных записаны три целых числа n, s и e (2 ≤ n ≤ 5000, 1 ≤ s, e ≤ n, s ≠ e) — количество стульев, начальная и конечная позиция Скотта.

Во второй строке записаны 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).

Выходные данные

Выведете минимальное количество секунд, которое придётся потратить Скотту, чтобы допрыгать до Кросса и посетить все стулья ровно по одному разу.

Пример
Входные данные
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
Примечание

В примере из условия возможным оптимальным решением является . Потраченное время равняется 17 + 24 + 23 + 20 + 33 + 22 = 139.