F. Фодволк

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

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

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

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

Энэ хаврын улирал болохоос өмнө нэгэн дэлгүүрт маш их хэмжээний фодволкнууд хямдрахаар болжээ. Нийтдээ $n$ ширхэг төрлийн фодволкнууд хямдрах байв. $i$-р төрлийн фодволк нь $c_{i}$ болон $q_{i}$ гэсэн 2 ширхэг параметртай бөгөөд энд $c_{i}$ нь уг фодволкны үнийг, $q_{i}$ нь чанарыг илэрхийлэх юм. Уг дэлгүүрт хямдралтай зарагдах эдгээр фодволкнууд тус бүрийг нь хязгааргүй тооны ширхэг байгаа гэж үзэх бөгөөд ерөнхийдөө чанарыг үнэтэй ямар нэгэн холбоогүй гэж үзнэ үү.

Таамаглаж байснаар дараагийн сард $k$ ширхэг үйлчлүүлэгч дэлгүүрт ирж үйлчлүүлэх бөгөөд $j$-р үйлчлүүлэгч нь $b_{j}$ хэмжээний мөнгийг фодволк худалдан авахад зарцуулахаар бэлдсэн байх ажээ.

Бүх үйлчлүүлэгч нар нь нэгэн ижил стратеги-тэй үйлчлүүлнэ. Эхлээд үйлчлүүлэгч нь хамгийн сайн чанартай фодволкноос боломжит хамгийн олон тоогоор нь худалдан авах бөгөөд дараа нь үлдсэн фодволкнуудын дундаас хамгийн сайн чанартай фодволкноос боломжит хамгийн олон тоогоор нь худалдан авна гэх мэтчилэн худалдан авалт хийх ажээ. Түүнчлэн ижилхэн чанар бүхий хэд хэдэн фодволкнууд дундаас үйлчлүүлэгч аль хямдхан фодволкийг нь худалдан авах юм. Үйлчлүүлэгч нар нь ижил фодволкнуудад дургүй учраас үйлчлүүлэгч болгон нь ямар нэгэн төрлийн фодволкноос хамгийн ихдээ нэг ширхэгийг худалдан авна. Энд фодволкны төрлийн талаар ярьж байгаа бөгөөд өмнө заасан нөхцөлд чанарын талаар ярьж байгаа тул эдгээрийг хооронд нь андуурахгүй байхыг хүсье.

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

Оролт

Оролтын эхний мөрөнд эерэг бүхэл тоо $n$ ($1 ≤ n ≤ 2*10^{5}$) өгөгдөх ба энэ нь фодволкны төрлүүдийн тоог илэрхийлнэ.

Дараагийн $n$ мөрийн мөр болгонд 2 бүхэл тоо $c_{i}$ болон $q_{i}$ ($1 ≤ c_{i}, q_{i} ≤ 10^{9}$) өгөгдөх ба эдгээр нь $i$-р төрлийн фодволкны үнэ болон чанарыг илэрхийлнэ.

Дараагийн мөрөнд үйлчлүүлэгчдийн тоог илэрхийлэх эерэг бүхэл тоо $k$ ($1 ≤ k ≤ 2*10^{5}$) өгөгдөнө.

Дараагийн мөрөнд $k$ ширхэг эерэг бүхэл тоо $b_{1}, b_{2}, ..., b_{k}$ ($1 ≤ b_{j} ≤ 10^{9}$)-ууд өгөгдөх ба эдгээрийн $j$-дахь тоо нь $j$-дахь үйлчлүүлэгчийн фодволкнууд худалдан авахад зарцуулахаар бэлдсэн мөнгөний нийт дүнг илэрхийлнэ.

Гаралт

Гаралтын эхний мөрөнд $k$ ширхэг бүхэл тоонуудын дарааллыг хэвлэх бөгөөд эдгээр тоонуудын $i$-дахь тоо нь $i$-р үйлчлүүлэгчийн худалдан авах фодволкны тоотой тэнцүү байх юм.

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

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

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

Тэмдэглэл

Эхний жишээнд эхний үйлчлүүлэгч нь эхлээд 2-р төрлийн фодволк худалдан авах ба дараа нь 1-р төрлийн фодволкноос худалдан авна. Тэрээр 10 төгрөг зарцуулах бөгөөд 3-р төрлийн фодволк нь 4 төгрөгийн үнэтэй учраас уг төрлийн фодволкноос худалдан авах боломжгүй болох ба ингэснээр уг үйлчлүүлэгч нь 3 төгрөгтэй үлдэх юм. 2-дахь үйлчлүүлэгч нь бүх 3 төрлийн фодволкнуудыг худалдан авах бөгөөд тодруулбал эхлээд 2-р төрлийн фодволк, дараа нь 1-р төрлийн фодволк болон 3-р төрлийн фодволкнуудыг тус тус худалдан авна. Ингэснээр тэрээр өөрийн бүх мөнгөө фодволк худалдан авалтад зарцуулах юм.

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