Скотт Ланг Даррен Кроссын эсрэг дайн зарлажээ. Танхимд $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$ дэхь сандал уруу үсэрвэл нийт:

• $|x_{i} - x_{j}| + c_{i} + b_{j}$ секунд хэрвээ $j < i$.
• $|x_{i} - x_{j}| + d_{i} + a_{j}$ секунд хэрвээ $j > i$.

Утгууд $x$, $a$, $b$, $c$, $d$-ыг өгөх бөгөөд Скотт сандал болгон дээр яг нэг удаа буун Кросс дээр очих хамгийн бага хугацааг ол.

Оролт

Эхний мөрөнд сандалны тоо, Скоттын эхлэл болон төгсгөлийн байрлалууд болох 3-н бүхэл тоонууд $n$, $s$, $e$ ($2 ≤ n ≤ 5000, 1 ≤ s, e ≤ n, s ≠ e$) өгөгдөнө.

2 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $x_{1}, x_{2}, ..., x_{n}$ ($1 ≤ x_{1} < x_{2} < ... < x_{n} ≤ 10^{9}$) өгөгдөнө.

3 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{1}, a_{2}, ..., a_{n} ≤ 10^{9}$) өгөгдөнө.

4 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $b_{1}, b_{2}, ..., b_{n}$ ($1 ≤ b_{1}, b_{2}, ..., b_{n} ≤ 10^{9}$) өгөгдөнө.

5 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $c_{1}, c_{2}, ..., c_{n}$ ($1 ≤ c_{1}, c_{2}, ..., c_{n} ≤ 10^{9}$) өгөгдөнө.

6 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $d_{1}, d_{2}, ..., d_{n}$ ($1 ≤ d_{1}, d_{2}, ..., d_{n} ≤ 10^{9}$) өгөгдөнө.

Гаралт

Скотт бүх сандал дээр яг нэг удаа буун Кроссын байгаа сандал дээр очих хамгийн бага хугацааг олж хэвлэнэ үү.

Жишээнд хамгийн тохиромжтой хариулт нь . Зарцуулагдсан нийт хугацаа $17 + 24 + 23 + 20 + 33 + 22 = 139$.