+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- جنگ جهانی هفدهم نزدیک است و کشورها خود را برای آن آماده می‌کنند. هر کشور تعدادی پادگان دارد و هر پادگان تعدادی سرباز دارد. هر کشور در جنگ تعدادی موج حمله بخصوص با مشخصه‌های مختلف دارد. اگر مشخصه‌ی موجی عدد طبیعی $x$ باشد، آنگاه هر پادگان آن کشور، تا زمانی که تعداد سربازانش از $x$ کمتر نشده، دسته‌های $x$ نفره برای آن موج اعزام می‌کند. تعداد اعضای هر موج را به عنوان افسر ارشد ارتش ارزشمند آن کشور بیابید. توجه کنید که **کشورها کاملاً از هم مستقل هستند** و نیز موج‌های یک کشور **به ترتیب** آماده می‌شوند و **افراد یک موج دیگر عضو پادگان نیستند** و بنابرین **هر سرباز در حداکثر یک موج** حضور می‌یابد. *برای درک بهتر خواسته سوال به توضیحات نمونه مراجعه کنید.* # ورودی در خط اول $c$ نمایانگر تعداد کشورها داده می‌شود و سپس اطلاعات $c$ کشور به ترتیب می‌آید. در سطر اول کشور $i$ـم دو عدد $n_i$ و $w_i$ به ترتیب از چپ می‌آید که $n_i$ تعداد پادگان‌های آن کشور و $w_i$ تعداد موج‌های آن کشور را نشان می‌دهد. در سطر بعد $n_i$ عدد با فاصله می‌آید که $j$ـمین آنها $a_{i,j}$ تعداد اعضای پادگان $j$ـم است. سپس در سطر بعد $w_i$ عدد با فاصله می‌آید که عدد $j$ـم $g_{i,j}$ مشخصه موج $j$ـم را نشان می‌دهد. $$1 \le c \le 1000$$ $$1 \le n_i, w_i, \sum_{i=1}^t n_i, \sum_{i=1}^t w_i, \le 100 \, 000$$ $$1 \le a_{i,j}, g_{i,j} \le 10^{12}$$ $$g_{i,1} > g_{i,2} > \dots > g_{i,w_i} \quad (1 \le i \le c)$$ # خروجی برای هر کشور در سطری جداگانه تعداد سربازان موج‌ها را به ترتیب خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 3 2 2 7 5 3 2 4 2 4 5 4 5 4 2 1 3 1000000000000 13831120 821120 415 ``` ## خروجی نمونه ۱ ``` 9 4 16 0 999989976000 9853440 170150 ``` در این مثال ۳ کشور در جنگ حضور دارند. کشور اول پادگان‌هایی با ۲، ۷ و ۵ سرباز دارد. در موج اول مشخصه ۳ است و به ترتیب ۰، ۶ و ۳ نفر از پادگان‌ها برای آن اعزام می‌شوند(در مجموع **۹** نفر) و ۲، ۱، ۲ نفر در پادگان‌ها باقی می‌مانند. در موج دوم که مشخصه ۲ است؛ به ترتیب ۲، ۰ و ۲ نفر اعزام می‌شوند(مجموعاً **۴** نفر) و نهایتا تنها یک نفر در پادگان دوم باقی می‌ماند و آن نفر در هیچ موجی شرکت نمی‌کند. کشور دوم چهار پادگان با ۴ ، ۵، ۴ و ۵ سرباز دارد. در موج اول که مشخصه ۴ هست، همه پادگان‌ها یک دسته ۴ نفره برای آن اعزام می‌کنند و در مجموع ۱۶ نفر اعزام می‌شوند و به ترتیب ۰، ۱، ۰ و ۱ نفر در پادگان‌ها می‌مانند. موج دوم مشخصه ۲ دارد، ولی از آنجا که هیچ پادگانی حداقل دو عضو ندارد، هیچ دسته‌ای اعزام نمی‌شود.

حل سؤال در بانک سؤالات