Taxi

در یک ترمینال تاکسیرانی، تعداد بسیار زیادی تاکسی در یک صف قرار دارند. ظرفیت هر تاکسی دقیقاً ‎۴‎ نفر است و هر تاکسی تنها زمانی ترمینال را ترک می‌کند که دقیقاً ‎۴‎ مسافر در آن نشسته باشد.

می‌دانیم تعداد تاکسی‌های موجود در ترمینال (در ابتدای روز) بسیار بسیار زیاد است و مسافرانِ ترمینال در دسته‌های ‎۱‎، ‎۲‎، ‎۳‎ یا ‎۴‎ نفره و در زمان‌های مشخص وارد ترمینال می‌شوند. هر مسافر (در هر دسته‌ای که باشد)، از زمان ورود به ترمینال تا زمانی که تاکسی‌ای که در آن نشسته حرکت کند احساس بی‌حوصلگی می‌کند و از این رو، اندازه‌ی این فاصله‌ی زمانی را «‎میزان نارضایتی‎» آن مسافر می‌گوییم.

برای مثال اگر یک گروه ‎۳‎ نفره در زمان ‎۱۰‎ و یک گروه ‎۱‎ نفره در زمان ‎۵۰‎ وارد ترمینال شوند و دو گروه در یک تاکسی بنشینند، مجموع نارضایتی تمام آن‌ها ‎۱۲۰‎ می‌شود.

اکنون از شما خواسته شده تا با دانستن زمان ورود و تعداد افراد دسته‌های مختلفی که وارد ترمینال می‌شوند، طوری مسافران را در تاکسی‌ها بنشانید که مجموع نارضایتی تمام مسافران کمینه شود. دقت کنید که تمام اعضای یک گروه باید الزاماً در یک تاکسی بنشینند. اما لزومی ندارد که یک گروه مسافر که تازه وارد ترمینال می‌شود در اولین تاکسی‌ای که جای کافی برای آن‌ها دارد، بنشیند‎!‎

برای مثال اگر ‎۴‎ گروه تک‌نفره در زمان‌های ‎۱‎ و ‎۲‎ و ‎۳‎ و ‎۴‎ وارد ترمینال شوند و پس از آن‌ها دو گروه سه‌نفره، یکی در زمان ‎۱۰‎ و دیگری در زمان ‎۱۱‎ وارد شوند و نهایتاً دو گروه تک‌نفره در زمان‌های ‎۱۰۱۰‎ و ‎۱۰۱۱‎ وارد ترمینال شوند، در این‌صورت دو تا از روش‌های ممکن عبارتند از:

• روش بدیهی‎: چهار گروه تک‌نفره در یک تاکسی نشسته و حرکت کنند. دو گروه ‎۳‎ نفره در تاکسی‌های شماره ‎۲‎ و ‎۳‎ بنشینند و دو نفر آخر نیز تاکسی‌های دوم و سوم را پر کنند تا این تاکسی‌ها نیز حرکت کنند. در این حالت میزان نارضایتی برای چهار گروه اوّل برابر ‎۶‎ و برای گروه‌های پنجم و ششم ‎(سه‌نفره)‎ برابر ‎۶۰۰۰‎ می‌شود، در نتیجه با این روش مجموع نارضایتی برابر ‎۶۰۰۶‎ خواهد بود.
• روش بهتر‎:‎ در راه دیگر نفرات اوّل و دوم در ‎۲‎ تاکسی مختلف نشسته و نفرات سوم و چهارم یک تاکسی ‎(سوم)‎ را اشغال می‌کنند. پس از آن گروه‌های سه نفره در تاکسی‌های اول و دوم می‌نشینند (نارضایتی ‎۱۸‎ برای دو نفر اول) تا دو تاکسی اوّل و دوم حرکت کنند. تاکسی سوم نیز با آمدن دو نفر آخر تکمیل می‌شود (نارضایتی ‎۲۰۱۶‎ برای نفرات سوم، چهارم و هفتم). در این روش مجموع کل نارضایتی‌ها ‎۲۰۳۴‎ می‌شود‎!‎

برنامه‌ای بنویسید که

• یک عدد ‎$n$ (تعداد گروه‌های مسافرین) و سپس ‎$n$‎ زوجِ ‎«تعداد گروه، زمان آمدن‎«‎ را از ورودی بخواند؛
• یک روش بهینه که کمترین مجموع نارضایتی را در پی داشته باشد ارائه کند.
• این کمترین مجموع نارضایتی را در خروجی بنویسد.

• در سطر اول ورودی، ‎$T$‎، تعداد سناریوهای تست آمده و در ادامه ‎$T$‎ بلوک به‌صورت زیر داده می‌شود.
• در خط اوّل هر بلوک عدد ‎$n$ (تعداد گروه‌های مسافرین) قرار دارد‎.
• در ‎$n$‎ سطر بعدی در هر سطر ابتدا تعداد مسافرین گروه و سپس زمان آمدن آن گروه داده می‌شود.
• تعداد سناریوهای هر تست حداکثر ‎۲۰‎ بوده و در هر سناریو ‎$1 \le n \le 1500$‎.
• زمان آمدن مسافرین تمام گروه‌ها صحیح، نامنفی و کوچک‌تر از ‎$10^9$‎ است.
• تعداد اعضای هر گروه حداقل یک و حداکثر ‎۴‎ است.

برای هر سناریوی ورودی‎:‎

• در صورتی که به هیچ روشی امکان ندارد در پایان کار تمام مسافرین از ترمینال خارج شوند (مثلاً تعداد کل مسافرین مضرب ‎۴‎ نباشد!) عبارت ‎No Solution‎ را در یک خط بنویسید.
• در غیر این‌صورت، در یک خط کمترین میزان نارضایتی (در بهترین روش) را بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل

‎