B. Инна, Дима ба дуу

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

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

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

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

Инна бол агуу төгөлдөр хуурч харин Дима бол даруухан гитарчин юм. Дима саяхан нэг дуу бичсэн бөгөөд тэд түүнийг хамтдаа тоглохыг хүсжээ. Мэдээж Серёжа дуу сонсохыг маш их хүсэж байгаа.

Дуу нь нотнуудын дараалал бөгөөд Дима, Инна хоёр нот бүрийг хамт тоглохыг хүсэж байгаа. Тиймээс тэд төгөлдөр хуур болон гитар хоёулан дээр нь зэрэг $i$-р нотыг $v$ ($1 ≤ v ≤ a_{i}$) хэмжээгээр тоглож чадна. Тэд тухайн нотны хөгийг хадгалах ёстой, тиймээс $i$-р нотыг төгөлдөр хуур болон гитар дээр $b_{i}$ хэмжээгээр тоглох ёстой. Хэрвээ Инна Дима хоёр тодорхойлсон дүрмээр нотыг тоглож чадахгүй бол түүнийг алгасах бөгөөд Серёжагийн баяр хөөр $1$-ээр буурна. Гэхдээ Инна Дима хоёр $i$-р нотыг харгалзан $x_{i}$ ба $y_{i}$ $(x_{i} + y_{i} = b_{i})$ хэмжээгээр тогловол Серёжагийн баяр хөөр $x_{i} \cdot y_{i}$-ээр нэмэгдэнэ.

Серёжа их сургуулиасаа гэртээ эргэж ирсэн бөгөөд түүний одоогийн баяр хөөр $0$ байна. Дууг сонссоны дараа Серёжагийн баяр хөөр хамгийн их байхаар дууг тоглоход Инна Дима хоёрт тусална уу.

Оролт

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

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь дууг сонссоны дараа Серёжагийн мэдэрсэн боломжит хамгийн их баяр хөөр юм.

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

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

Оролт
3
1 1 2
2 2 3
Гаралт
4
Оролт
1
2
5
Гаралт
-1

Тэмдэглэл

Эхний жишээнд Инна Дима хоёр эхний хоёр нотыг $1$ хэмжээгээр ($1 + 1 = 2$, нөхцлийг хангана) тоглох бөгөөд, сүүлийн нотыг $1$ ба $2$ хэмжээнүүдээр тоглоно. Серёжагийн баяр хөөр нь $1\cdot 1 + 1\cdot 1 + 1\cdot 2 = 4$ байна.

Хоёр дахь жишээнд $1 ≤ x, y ≤ 2$, $x + y = 5$ байх $(x, y)$ хос байхгүй учраас Инна Дима хоёр нотыг алгасана. Тиймээс Серёжагийн баяр хөөр $-1$ байна.

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