C. Геометр морь

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

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

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

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

Вася Геометр морь гэдэг тоглоом тоглодог.

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

Нийт $n$ төрлийн геометрийн дүрсүүд байна. Төрөл бүрийн дүрсийн хувьд тухайн дүрсийн төрлийн дугаар $k_{i}$ болон тухайн дүрсийн үнэ $c_{i}$ мэдэгдэж байх юм. Тоглогч нь $i$ төрлийн нэг дүрсийг устгаад $c_{i}*f$ оноо авах ба энд $f$ нь одоогийн үржүүлэгч байна. Үржүүлэгчийн утга нь $1$-ээс $t + 1$ хүртэлх (эдгээр нь өөрсдөө байж болно) бүхэл тоо байх юм. Тоглоом эхлэхэд үржүүлэгч утга нь 1-тэй тэнцүү байна. $p_{i}$ $(1 ≤ i ≤ t)$ ширхэг дүрсүүдийг устгасны дараа үржүүлэгч нь $i + 1$ болох ба иймд $(p_{i} + 1)$-дахь дүрсийг устгахдаа бид үржүүлэгчийг $i + 1$-тэй тэнцүү гэж үзэх юм.

Таны даалгавар бол Вася бүх дүрсүүдийг устгасны дараа авч болох хамгийн их оноог тодорхойлох юм. Вася маш хэцүү бөгөөд өөрийн сонгосон дарааллаар дүрсүүдийг устгана гэдгийг анхаарна уу.

Оролт

Эхний мөрөнд дүрсүүдийн төрлийн тоо болох ганц бүхэл тоо $n$ $(1 ≤ n ≤ 100)$ өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 2 бүхэл тоо $k_{i}$ болон $c_{i}$ $(1 ≤ k_{i} ≤ 10^{9}, 0 ≤ c_{i} ≤ 1000)$ өгөгдөх ба эдгээр нь харгалзан $i$-дахь төрлийн дүрсүүдийн тоо болон $i$-дахь төрлийн дүрсийн үнийг илэрхийлнэ.

Дараагийн мөрөнд үржүүлэгчийн өөрчлөлтүүдийн тоог илэрхийлэх ганц бүхэл тоо $t$ $(1 ≤ t ≤ 100)$ өгөгдөнө.

Дараагийн мөрөнд зайгаар тусгаарлагдсан $t$ ширхэг бүхэл тоо $p_{i}$ $(1 ≤ p_{1} < p_{2} < ... < p_{t} ≤ 10^{12})$-ууд өгөгдөнө.

С++ дээр 64-битийн бүхэл тоонуудыг унших болох бичихдээ %lld тодорхойлогчийг битгий ашиглана уу. cin, cout streams эсвэл %I64d тодорхойлогч ашиглахыг илүүд үзнэ үү.

Гаралт

Вася-ын авч болох хамгийн их оноог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
1
5 10
2
3 6
Гаралт
70
Оролт
2
3 8
5 10
1
20
Гаралт
74

Тэмдэглэл

Эхний жишээнд Вася эхлээд 3-н дүрс устгах ба $3*1*10 = 30$ оноо авах юм. Дараа нь үржүүлэгч нь $2$ болох ба сүүлийн 2 дүрсийг устгасны дараа тэрээр $2*2*10 = 40$ оноо авна. Ингэснээр Вася нийт $70$ оноо авах юм.

2-дахь жишээнд бүх $8$-н дүрсүүд нь $1$ гэсэн үржүүлэгчтэйгээр устгагдах ба ингэснээр Вася $(3*8 + 5*10)*1 = 74$ оноо авна.

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