A. Максим ба хөнгөлөлт

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

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

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

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

Максим ням гараг бүр дэлгүүр явдаг. Өнөөдөр супермаркетын хөнгөлөлтийн систем тусгай үнэ санал болгож байна.

Хөнгөлөлтийн $m$ ширхэг төрөл байдаг. Бид хөнгөлөлтийг $1$-ээс $m$ хүртэл дугаарлагдсан гэж үзнэ. $i$-р хөнгөлөлтийг хэрэглэхийн тулд үйлчлүүлэгч түүний худалдан авсан яг $q_{i}$ барааг хийдэг онцгой сагс авна. Хөнгөлөлтийн системийн нөхцлийн дагуу үйлчлүүлэгч супермаркетаас хамгийн ихдээ хоёр барааг сагсандаа үнэгүй нэмж авч болно. Үйлчлүүлэгчийн сонгосон "үнэгүй бараа"-ны тоо $0$ эсвэл $1$ эсвэл $2$ байна. Сонгож авсан "үнэгүй бараа"-нд дараах нөхцөл тавигдана: "үнэгүй бараа" бүр нь сагсанд байгаа $q_{i}$ ширхэг барааны хамгийн хямдаас нь илүү үнэтэй байж болохгүй.

Максим одоо дэлгүүрээс $n$ бараа худалдан авах хэрэгтэй байгаа. Тэр хөнгөлөлтийн системийг хамгийн оновчтойгоор ашигласан бол тэдгээр барааг худалдан авахад Максимд хэрэгтэй хамгийн бага үнийн дүнг ол.

Ямар ч үйлдэл хийсэн супермаркетэд хангалттай сагс байгаа гэж үзнэ. Максим ижил хөнгөлөлтийг хэд хэдэн удаа ашиглаж чадна. Мэдээж хэрэг Максим хөнгөлөлттэй ямар ч барааг худалдан авч болно.

Оролт

Эхний мөрөнд хөнгөлөлтийн төрлийн тоо болох $m$ $(1 ≤ m ≤ 10^{5})$ бүхэл тоо байна. Хоёр дахь мөрөнд $m$ ширхэг бүхэл тоонууд байна: $q_{1}, q_{2}, ..., q_{m}$ $(1 ≤ q_{i} ≤ 10^{5})$.

Гурав дахь мөрөнд Максимд хэрэгтэй бараануудын тоо болох $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоо байна. Дөрөвдүгээр мөрөнд $n$ ширхэг бүхэл тоо байна: $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{4})$. Эдгээр нь бараануудын үнэ юм.

Бүх тоонуудыг зайгаар тусгаарлан бичнэ.

Гаралт

Нэг мөрөнд нэг бүхэл тоо хэвлэнэ.

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

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

Оролт
1
2
4
50 50 100 100
Гаралт
200
Оролт
2
2 3
5
50 50 50 50 50
Гаралт
150
Оролт
1
1
7
1 1 1 1 1 1 1
Гаралт
3

Тэмдэглэл

Эхний жишээнд Максим $100$ үнэтэй хоёр барааг аваад хөнгөлөлтөөр $50$ үнэтэй хоёр барааг үнэгүй авна. Энэ тохиолдолд Максим $200$-г төлнө.

Хоёрдугаар жишээнд Максим $3$ ширхэг барааг аваад хөнгөлөлтөөр $2$ ширхэг барааг үнэгүй авна. Энэ тохиолдолд Максим $150$-г төлнө.

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