C. Калила Димна хоёр мод бэлтгэх үйлдвэр дээр

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

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

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

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

Калила, Димна бол асар том ширэнгэн ойд амьдардаг хоёр чоно юм. Нэг өдөр тэд мөнгө олохын тулд мод бэлтгэх үйлдвэрт ажиллахаар шийджээ.

Модны үйлдвэрийн менежер тэднээс ой руу явж $a_{1}, a_{2}, ..., a_{n}$ өндөртэй $n$ мод тайрахыг хүсэв. Тэд дэлгүүрээс хөрөөний гинж худалдаж авсан байна. Тэд $i$ дугаартай модонд хөрөөний гинжээ хэрэглэх бүрдээ тухайн модны өндрийг нэг нэгжээр бууруулж чадна. Мөн тэд хөрөөний гинжийг хэрэглэх бүрдээ дахин цэнэглэх хэрэгтэй. Цэнэглэх зардал нь бүрэн (хэрвээ модыг бүрэн тайрсан бол түүний өндөр 0 байна) тайрч авсан моднуудын дугаараас хамаарна. Хэрвээ бүрэн тайрсан модны хамгийн их дугаар $i$ бол (эхэндээ мод $a_{i}$ өндөртэй байсан) хөрөөний гинжийг цэнэглэх зардал $b_{i}$ байх болно. Хэрвээ ямар ч мод бүрэн тайраагүй бол Калила, Димна хоёр хөрөөний гинжийг цэнэглэж чадахгүй. Хөрөөний гинжийг эхлээд цэнэглэнэ. $i$ < $j$, $a_{i} < a_{j}$ ба $b_{i} > b_{j}$ мөн $b_{n} = 0$ ба $a_{1} = 1$ болохыг бид мэддэг. Калила болон Димна нар бүх модыг хамгийн бага зардлаар бүрэн тайрахыг хүсэж байна.

Тэд таныг тэдэнд туслахыг хүсэж байна! Харин та?

Оролт

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

$a_{1} = 1$, $b_{n} = 0$, $a_{1} < a_{2} < ... < a_{n}$ ба $b_{1} > b_{2} > ... > b_{n}$ гэдэг нь баталгаатай байна.

Гаралт

Гаралтын нэг мөр бүх модыг тайрах хамгийн бага зардлыг агуулсан байх ёстой.

С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой.

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

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

Оролт
5
1 2 3 4 5
5 4 3 2 0
Гаралт
25
Оролт
6
1 2 3 10 20 30
6 5 4 3 2 0
Гаралт
138
Сэтгэгдлүүдийг ачааллаж байна...