E. Уралдаан зохион байгуулах

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

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

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

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

Кэколэнд бол зүүнээсээ баруун тийш дугаарлагдсан, хоорондоо $n - 1$ замаар холбогдсон $n$ ширхэг үзэсгэлэнт хоттой улс юм. $i$ болон $i + 1$-р хотыг холбосон замын дугаар нь $i$ ба энэ замын урт нь $w_{i}$ километр.

Кэколэндэд машин барих үедээ та $i$-р хотод машинаар ирэх бүртээ $g_{i}$ литр шатахуунтай болно. Кэколэндэд өөрөөр шатахуунтай болох ямар ч аргагүй.

Кэколэндийн ерөнхийлөгч Кеко таныг Кэколэндэд урьд өмнө нь байгаагүй тийм үзэсгэлэнтэй уралдаан зохиолгохоор хөлслөсөн. Уралдааныг $l$ болон $r$ ($l ≤ r$) хотуудын хооронд болно гэж үзье. Уралдаан хоёр үетэй байна. Эхний үед машинууд $l$ хотоос $r$ хотруу уралдана. Эхний үеийн дараа буюу дараагийн өдөр хоёрдугаар үе явагдах ба энэ удаад уралдаанд оролцогчид $r$ хотоос $l$ хотруу уралдана. Мэдээж уралдаж байгаа учир уралдаанд оролцогчид эхлэж буй хотоос дуусах хотруу шууд чиглэн явна. Энэ нь эхний үед тэд зөвхөн баруун тийш явах бол хоёрдугаар үед зөвхөн зүүн тийш явна гэсэн үг. $l$ ба $r$ хотын хоорондох уралдаанд тамирчид Кэколэндийн $r - l + 1$ үзэсгэлэнтэй хотоор дайрах учир энэ уралдааны үзэсгэлэнтэй гэх хэмжүүр нь $r - l + 1$-тай тэнцүү. Машинуудын шатахууны савны хэмжээ хязгааргүй ба тамирчид тэдэнд өгсөн бүх шатахууныг авах болно.

Үе бүрийн эхэнд тамирчид уралдаанаа хоосон шатахууны савтай эхэлнэ ($0$ литр шатахуунтай). Тэд эхлэх хотоос уралдаан эхэлсний яг дараа нь өөрсдийн шатахуунаа авна (эхний үеийн хувьд $l$ хотоос хоёрдугаар үеийн хувьд $r$ хотоос).

Хэрвээ машинуудын шатахуун барианд хүрэхээс өмнө дуусахаар байвал $l$ ба $r$ хотуудын хооронд уралдаан зохиох боломжгүй байж болно.

Танд $k$ бэлэг байгаа. Та $i$ хотод бэлэг өгөх бүрт хотын $g_{i}$ утга $1$-р нэмэгдэнэ. Та бэлгээ хотуудад дурын замаар тарааж болно (нэг хотод олон бэлэг өгч болно). Таны зохиож чадах хамгийн үзэсгэлэнтэй уралдаан юу вэ?

Машин бүр километр тутамд $1$ литр шатахуун зарцуулна.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($2 ≤ n ≤ 100 000$, $0 ≤ k ≤ 10^{9}$) байх ба харгалзан Кэколэнд дахь хотуудын тоо ба танд байгаа бэлэгний тоо байна.

Дараагийн мөрөнд $n - 1$ бүхэл тоо байна. Эдгээрийн $i$-р тоо нь $w_{i}$ ($1 ≤ w_{i} ≤ 10^{9}$) байх ба $i$ болон $i + 1$ хотуудын хоорондох замын урт байна.

Дараагийн мөрөнд $n$ бүхэл тоо байна. Эдгээрийн $i$-р тоо нь $g_{i}$ ($0 ≤ g_{i} ≤ 10^{9}$) байх ба та $i$-р хотод ирэх бүртээ авах шатахууны хэмжээ.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
4 4
2 2 2
1 1 1 1
Гаралт
4
Оролт
8 5
2 2 2 3 7 3 1
1 3 1 5 4 0 2 5
Гаралт
7

Тэмдэглэл

Эхний жишээн дээр хэрвээ та хот бүрт нэг бэлэг өгвөл $1$ ба $4$ хотуудын хооронд уралдаан зохиох боломжтой болно.

Хоёр дахь жишээн дээр та $g_{5}$ дээр $1$-г харин $g_{6}$ дээр $4$-г нэмбэл $2$ ба $8$ хотуудын хооронд уралдаан зохиох боломжтой болно.

Сэтгэгдлүүдийг ачааллаж байна...