E. Дразил ба парк

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дразил гэдэг нэгэн сармагчин дугуй хэлбэртэй паркад амьдардаг. Паркыг тойроод $n$ ширхэг моднууд байдаг. $i$-р мод болон ($i + 1$)-р моднууд хоорондоо $d_{i}$ зайтай, харин $n$-р мод болон нэгдүгээр моднууд хоорондоо $d_{n}$ зайтай. Мөн $i$-р мод $h_{i}$ өндөртэй юм.

Дразил өглөө бүр гүйдэг. Түүний өглөөний гүйлт дараах алхмуудаас бүрдэнэ:

  • Дразил ялгаатай хоёр мод сонгоно
  • Тэгээд тэр эхний мод руу авирна
  • Дараа нь тэр эхний модноос буугаад паркыг тойрон (аль нэг чигт) гүйж хоёр дахь модон дээр очоод дээшээ авирна
  • Эцэст нь хоёр дахь модноос бууна.

Гэхдээ зарим дараалсан моднуудын эргэн тойронд хүүхдүүд байнга тоглож байдаг. Дразил хүүхдүүдтэй байж чадахгүй учраас тэдэнтэй ойрхон байгаа моднуудыг сонгож болохгүй. Тэр бүү хэл эдгээр моднуудад ойртож ч чадахгүй.

Дразил $x$ болон $y$-р модыг сонгосон бол бид түүний өглөө гүйхдээ авч чадах энергийг $2(h_{x} + h_{y}) + dist(x, y)$ томъёогоор тооцож чадна. $x$ ба $y$ моднуудыг холбосон хоёр нумны (хагас тойрог) аль нэг дээр нь хүүхдүүд тоглож байгаа тул эдгээр моднуудын хоорондын зай болох $dist(x, y)$-г хүүхдүүд тоглоогүй талаар тодорхойлно.

Та $i$-р өдөр $a_{i}$-р модноос $b_{i}$-р моднуудын хооронд хүүхдүүд тоглодог гэдгийг мэдэж байгаа. Томъёолбол хэрвээ $a_{i} ≤ b_{i}$ бол хүүхдүүд $[a_{i}, b_{i}]$ завсрын дугааруудтай моднуудын эргэн тойронд тоглож байгаа, эсрэг тохиолдолд $[a_i, n] \cup [1, b_i]$ хүртэлх дугаартай моднуудын эргэн тойронд тоглож байгаа.

Хамгийн их энерги (тэр эрүүл чийрэг янзтай сармагчин болохыг хүсдэг учраас) зарцуулахын тулд ямар хоёр мод сонгох ёстойг тодорхойлоход Дразилд туслана уу, Мөн өдөр бүрийн энергийн хэмжээг тайлагнаарай.

Оролт

Эхний мөрөнд $n$, $m$ ($3 ≤ n ≤ 10^{5}$, $1 ≤ m ≤ 10^{5}$) хоёр бүхэл тоо байна, эдгээр нь харгалзан моднуудын тоо болон өдрүүдийн тоог илэрхийлнэ.

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

Гурав дахь мөрөнд моднуудын өндрийг илэрхийлсэн $n$ ширхэг $h_{1}, h_{2}, ..., h_{n}$ ($1 ≤ h_{i} ≤ 10^{9}$) бүхэл тоонууд байна.

Дараа нь шинэ өдөр бүрийг тодорхойлсон $m$ мөрүүд байх ба мөр бүр $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) хоёр бүхэл тоог агуулна. Дразилын сонгож чадах, хүүхдүүд тоглоогүй мод дор хаяж хоёр ширхэг байна.

Гаралт

Өдөр бүрийн хариултыг тусдаа мөрүүдэд хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
5 3
2 2 2 2 2
3 5 2 1 4
1 3
2 2
4 5
Гаралт
12
16
18
Оролт
3 3
5 1 4
5 1 4
3 3
2 2
1 1
Гаралт
17
22
11
Сэтгэгдлүүдийг ачааллаж байна...