C. Захиалгын систем

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

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

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

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

Шинэлэг технологиуд гариг даяар ялалтын аян өрнүүлж байна. Тэд хүний үйл ажиллагааг бүгдийг нэгтгэж байна.

"Дижкстрагийн газар" гэх нэртэй ресторан захиалгын системээ оновчлох талаар бодож эхэлсэн.

Яг одоо ирчихсэн байгаа $n$ захиалгын хүсэлт байна. Хүсэлт бүр хоёр тоогоор тодорхойлогдоно: $c_{i}$ ба $p_{i}$ буюу харгалзан энэ хүсэлтээр ирэх зочдын хэмжээ ба тэдний ресторанд үрэх мөнгөний хэмжээ байна.

Бид хүсэлт бүрийн хувьд бүх $c_{i}$ хүн нэг ширээнд суухыг хүсч байгаа ба тэд 18:00 цагаас хаах хүртэлх бүхэл оройжингоо ресторанд байхыг хүсч байгааг мэдэж байна.

Харамсалтай нь ресторанд зөвхөн $k$ ширээ байгаа. Ширээ бүрийн хувьд бид энэ ширээн дээр сууж болох хүний хамгийн их тоо болох $r_{i}$-г мэдэж байгаа. Ширээн дээр зөвхөн нэг захиалгын хүмүүс л сууна. Хэрвээ та нэг захиалгын бүх хүмүүст хүрэлцэхээр том ширээ олж чадахгүй бол бүх зочид явах ба юу ч төлөхгүй.

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

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 1000$) байх буюу зочдоос ирсэн хүсэлтүүдийн тоо юм. Мөр бүрт хоёр бүхэл тоо $c_{i}, p_{i}$ $(1 ≤ c_{i}, p_{i} ≤ 1000$) байх буюу харгалзан $i$-р хүсэлтээр ирэх зочдын хэмжээ болон тэд ресторанд ирэхдээ төлөх мөнгөний нийт дүн байна.

Дараагийн мөрөнд бүхэл тоо $k$ ($1 ≤ k ≤ 1000$) байх ба ресторан дахь ширээнүүдийн тоо байна. Сүүлийн мөрөнд $k$ зайгаар тусгаарлагдсан бүхэл тоо $r_{1}, r_{2}, ..., r_{k}$ $(1 ≤ r_{i} ≤ 1000)$ байх ба ширээ бүрт суух хүмүүсийн хамгийн их тоонууд юм.

Гаралт

Эхний мөрөнд хоёр бүхэл тоо $m, s$ хэвлэх ба харгалзан зөвшөөрөгдсөн хүсэлтүүдийн тоо болон уг хүсэлтүүдээс ирэх мөнгөний нийт хэмжээ байна.

Тэгээд $m$ мөр хэвлэх ба мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоо байх буюу зөвшөөрөгдсөн хүсэлтийн дугаар ба уг хүсэлтээр ирэх зочдын суух ширээний дугаар байна. Хүсэлтүүд болон ширээнүүд оролтонд өгөгдсөн дарааллаараа $1$-с эхлэн дугаарлагдана.

Хэрвээ хэд хэдэн тохиромжтой хариулт байвал алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3
10 50
2 100
5 30
3
4 6 9
Гаралт
2 130
2 1
3 2
Сэтгэгдлүүдийг ачааллаж байна...