D. Гутлын дэлгүүр

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

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

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

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

Дэлгүүрийн агуулахад $n$ ширхэг хос гутал байгаа. Хос бүр нь үнэ $c_{i}$ болон гутлын хэмжээ (размер) $s_{i}$ гэсэн $2$ бүхэл тоогоор тодорхойлогдоно. Бид өнөөдөр $s_{i}$ бүх дугаарууд ялгаатай гэдгийг олж мэдлээ. Энэ нь хэмжээ бүрээс нэгээс олон хос байхгүй гэсэн үг юм.

Дэлгүүрт нэгэн зэрэг $m$ тооны хэрэглэгчид ирдэг. $i$-р хэрэглэгчийн өмсдөг гутлын хэмжээ $l_{i}$ ба тэр $d_{i}$ хэмжээний мөнгөтэй яваа. Хэрэв, $c_{j} ≤ d_{i}$ гэсэн нөхцөл биелээд, $l_{i} = s_{j}$ эсвэл $l_{i} = s_{j}-1$ байх юм бол $i$-р хэрэглэгч $j$-р хос гутлыг авч болно. Өөрөөр хэлбэл, хэрэглэгч гутал авах хангалттай мөнгөтэй байх, мөн сонгосон гуталныхаа хэмжээнээс $1$-ээр бага эсвэл үүнтэй тэнцүү размерын гутал өмсөх боломжтой.

Таны даалгавар бол ашиг буюу зарагдсан $c_{j}$ хос гутлуудын нийт дүнг хамгийн их байлгахаар хэрэглэгчдэд гуталнуудыг (нэг хүнд нэг хос гутал) зарах явдал юм. Энд хэрэглэгч нэгээс илүү хос авахгүй ба хос бүр нь нэгээс илүү хэрэглэгчдэд зарагдахгүй.

Оролт

Оролтын эхний мөр нь агуулахад байгаа хос гутлын тоог харуулах $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна. Дараагийн $n$ мөрүүд нь хос гутлын тодорхойлолтыг харуулах, хоосон зайгаар тусгаарлагдсан $c_{i}$ болон $s_{i}$ ($1 ≤ c_{i}, s_{i} ≤ 10^{9}$) бүхэл тоонуудыг агуулна. Энд, $s_{i}$ тоонууд ялгаатай байна.

Дараагийн мөр нь дэлгүүрийн хэрэглэгчдийн тоог харуулах $m$ ($1 ≤ m ≤ 10^{5}$) бүхэл тоог агуулна. Дараагийн $m$ мөрүүд нь хэрэглэгчдийн тодорхойлолтыг харуулах, хоосон зайгаар тусгаарлагдсан $d_{i}$ болон $l_{i}$ ($1 ≤ d_{i}, l_{i} ≤ 10^{9}$) тоонуудыг агуулна.

Гаралт

Эхний мөрөнд гутлуудыг зарснаар олж болох хамгийн их ашгийг илэрхийлэх бүхэл тоог хэвлээрэй. $2$ дахь мөрөнд зарах гутлын тоо $k$ бүхэл тоог хэвлээрэй. Дараагийн $k$ мөрүүдэд хоосон зайгаар тусгаарлагдсан $2$ бүхэл тоог хэвлээрэй. Энд эхний тоо хэрэглэгчийн дугаар байх ба $2$ дахь тоо нь хэрэглэгчийн авах гутлын дугаар байна. Энэ $k$ мөрүүдийг ямар ч дарааллаар хэвлэж болно.

Оролтод өгсөн дараалалд хэрэглэгчийн дугаар болон хос гутлын дугаар нь $1$-ээс эхлэн дугаарлагдсан байна. Оновчтой хариулт олон байвал аль нэгийг нь хэвлэж болно.

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

Орчуулсан: Солонго

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

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