زبل، مسئول تور گردشگری، تعداد محدودی از اتاق‌های هتل را برای مشتریانش رزرو کرده است. اتاق‌ها ظرفیت‌های متفاوتی و طبیعتا، قیمت‌های متفاوتی دارند. زبل تصمیم گرفت که کم‌هزینه‌ترین روش برای تخصیص اتاق به گردشگران را پیدا کند. استراتژی او پر کردن اتاق‌ها با مجموعه افراد مناسب برای کمینه کردن هزینه‌ی کل است اما او با این محدودیت مواجه است که هر دو نفر حاضر در اتاق که با هم ازدواج نکرده‌اند باید از یک جنسیت باشند و اگر یک اتاق به دو نفر که با هم ازدواج کرده‌اند تخصیص داده شود،‌ هیچ فرد دیگری نمی‌تواند در آن اتاق باشد. توجه کنید که لازم نیست دو نفر که با هم ازدواج کرده‌اند در یک اتاق باشند. همچنین لازم نیست که درون هر اتاق دقیقا به تعداد ظرفیتش مسافر باشد.

شما باید برنامه‌ای بنویسید که به زبل کمک کند که یک تخصیص دهی اتاق‌های رزرو شده‌ی هتل به گردشگران با هزینه‌ی کمینه پیدا کند.

در خط اول ورودی تنها یک عدد $t$، تعداد سناریوها آمده است. خط اول هر سناریو شامل چهار عدد است. $0 \le m \le 500$ تعداد گردشگران مرد، $0 \le f \le 500$ تعداد گردشگران زن، $0 \le r \le 500$ تعداد اتاق‌هایی که زبل رزرو کرده است و $c \ge 0$ که تعداد جفت‌هایی که با هم ازدواج کرده‌اند را نشان می‌دهد. توجه کنید که در این تور گردشگری هر کس یا مجرد است یا یک همسر یکتا دارد.

در $r$ خط بعدی اطلاعات اتاق‌ها می‌آید. هر خط یک اتاق را با دو عدد مشخص می‌کند. $1 \le b_i \le 5$ و $1 \le p_i \le 1000$ که به ترتیب ظرفیت و قیمت آن اتاق هستند.

به ازای هر سناریوی ورودی هزینه‌ی کمینه برای تخصیص اتاق به گردشگران را در یک خط چاپ کنید. اگر چنین کاری ممکن نیست کلمه‌ی Impossible را چاپ کنید.

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

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