D. Үнэг ба үсрэлт

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

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

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

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

Сиел үнэг тоглоом тоглож байна. Энэ тоглоомонд бүхэл тоонуудаар (эерэг, сөрөг, тэг) дугаарлагдсан нүднүүд бүхий хязгааргүй урттай тууз байдаг. Эхлээд тэр $0$ дугаартай нүдэнд зогсож байгаа.

Мөн $n$ тооны карт байгаа. Карт бүр $c_{i}$ үнэ, $l_{i}$ урттай. Хэрвээ тэр $c_{i}$ үнэ төлвөл $i$-р картыг ашиглах боломжтой болно. $i$-р картыг ашиглан $l_{i}$ урттай үсрэлт хийх боломжтой болох юм, өөрөөр хэлбэл $x$ нүднээс $(x-l_{i})$ нүд рүү, эсвэл $(x+l_{i})$ нүд рүү үсэрч чадна.

Сиел үнэг туузан дээрх дурын нүд рүү үсрэн очих боломжтой байхыг хүсэж байгаа. Энэ зорилгодоо хүрэхийн тулд тэр аль болох бага мөнгө төлөөд тодорхой тооны карт худалдаж авахыг хүсэж байгаа.

Хэрвээ энэ боломжтой бол төлөх хамгийн бага үнийн дүнг тооцоол.

Оролт

Эхний мөр нь картуудын тоо болох $n$ ($1 ≤ n ≤ 300$) бүхэл тоог агуулна.

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

Гурав дахь мөр нь картуудын үнийг илэрхийлэх $n$ ширхэг $c_{i}$ ($1 ≤ c_{i} ≤ 10^{5}$) тоонуудыг агуулна.

Гаралт

Хэрвээ бүх картыг худалдаж аваад ч дурын нүд рүү үсрэн хүрч чаддаг болох боломжгүй бол "-1" гэж хэвлэнэ. Эсрэг тохиолдолд хэрэгцээтэй картуудыг худалдаж авах хамгийн бага үнийг хэвлэнэ.

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

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

Оролт
3
100 99 9900
1 1 1
Гаралт
2
Оролт
5
10 20 30 40 50
1 1 1 1 1
Гаралт
-1
Оролт
7
15015 10010 6006 4290 2730 2310 1
1 1 1 1 1 1 10
Гаралт
6
Оролт
8
4264 4921 6321 6984 2316 8432 6120 1026
4264 4921 6321 6984 2316 8432 6120 1026
Гаралт
7237

Тэмдэглэл

Эхний жишээнд нэг карт худалдаж авах нь хангалттай биш юм. Жишээлбэл хэрвээ та $100$ урттай картыг худалдаж авбал $100$-д хуваагддаггүй дугаартай нүд рүү үсэрч чадахгүйд хүрнэ. Тиймээс эхний болон хоёрдугаар картыг худалдаж авах нь хамгийн зөв сонголт юм. Ингэснээр та аль ч нүд рүү үсрэх боломжтой болно.

Хоёр дахь жишээнд та бүх картыг авсан ч $10$-д хуваагддаггүй дугаартай нүд рүү үсэрч чадахгүй. Тиймээс хариу нь "-1" байна.

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