Masala #HR8QXELMMB

Magazinga bahor faslining boshlanishidan oldin katta miqdordagi futbolkalar sotuvga qo'yiladi. Umumiy holda sotuvga n turdagi futbolkalar qo'yiladi. i-turdagi futbolkaning ikkita butun son ko'rsatkichi bor — c[i] va q[i], bu yerda c[i] — bu i-turdagi futbolkaning narxi, q[i] esa i-turdagi futbolkaning sifati. Do'konda har bir turdagi futbolkalardan cheksiz miqdorda mavjud deb hisoblash kerak, lekin umumiy holda sifat narx bilan bog'liq emas.

Bashoratlarga ko'ra, keyingi oyda do'konga k nafar xaridor keladi, j-xaridor futbolkalarga b[j] gacha pul sarflashga tayyor.

Barcha xaridorlar bir xil strategiyaga ega. Avval xaridorlar maksimal sifatli futbolkalarni maksimal miqdorda sotib olishni xohlaydilar, keyin qolgan futbolkalar orasidan eng sifatli futbolkalarni maksimal miqdorda sotib olishadi, shuningdek, bir xil sifatli futbolkalar orasida eng arzonini tanlashadi. Xaridorlar bir xil futbolkalarni yoqtirmaydilar, shuning uchun har bir xaridor bir turdagi futbolkadan bitta sotib oladi.

Agar xaridorlar yuqorida ta'riflangan strategiyaga amal qilsalar, har bir xaridor qancha futbolka sotib olishini aniqlang. Barcha xaridorlar bir-biridan mustaqil ravishda harakat qilishadi va birining xaridi boshqasiga ta'sir qilmaydi.

Birinchi qatorda musbat butun son n (1 ≤ n ≤ 2·10⁵) — futbolkalar turlari soni.

Keyingi n qatorning har birida ikki tadan butun son c[i] va q[i] (1 ≤ ci, qi ≤ 10⁹) — i-turdagi futbolkaning narxi va sifati beriladi.

Keyingi qatorda musbat butun son k (1 ≤ k ≤ 2·10⁵) — xaridorlar soni beriladi.

Keyingi qatorda k ta musbat son b[1], b[2], ..., b[k] (1 ≤ b[j] ≤ 10⁹) keltirilgan bo'lib, har bir j-soni j-xaridor futbolkalarga sarflashga tayyor bo'lgan pul miqdorini bildiradi.

Chiqishda har bir xaridor qancha futbolka sotib olishini bildiruvchi k ta butun sondan iborat qator chiqarilishi kerak.