رژیم مالی


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

استاد که بدن خوش فرمی دارد، نیاز به رژیم غذایی ندارد ولی متأسفانه خرج‌هایش زیاد شده و در رژیم مالی به سر می‌برد. از طرفی استاد کوله‌باری از افتخارات جمع‌کرده و شام‌های زیادی به دوستانش بدهکار است. در هر شام تعدادی سیخ کباب و تعدادی سیخ جوجه باید برای دوستانش تهیه کند.

رستوران‌هایی که استاد به آن‌ها مراجعه می‌کند سه غذا دارند که هر کدام قیمت خاصی دارد. «خوراک کباب» که از دو سیخ کباب تشکیل شده، «خوراک جوجه» که از دو سیخ جوجه تشکیل شده و «خوراک میکس» که از یک سیخ کباب و یک سیخ جوجه تشکیل شده‌است. به استاد در پیدا کردن کمترین هزینه هر شام کمک کنید.

ورودی🔗

در خط اول tt تعداد افتخارات استاد می‌آید و سپس اطلاعات tt شام به ترتیب می‌آید.

1t100,0001 \le t \le 100,000

خط اول توضیحات شام iiام دو عدد kik_i و jij_i می‌آیند که به ترتیب از چپ حداقل تعداد کباب‌ها و جوجه‌هایی که استاد باید آن شب بخرد را نشان می‌دهند.

0ki,ji1,000,0000 \le k_i, j_i \le 1,000,000

در سطر بعد سه عدد KabaabiKabaab_i، JoojehiJoojeh_i و MixiMix_i می‌آید که به‌ترتیب از چپ نشان‌گر قیمت «خوراک کباب»، «خوراک جوجه» و «خوراک میکس» است.

1Kabaabi,Joojehi,Mixi10001 \le Kabaab_i, Joojeh_i, Mix_i \le 1000

خروجی🔗

به ترتیب، کمترین خرجی که استاد باید برای هر شام بکند را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4
2 2
1 2 2
1 5
10 1 2
3 1
7 7 3
0 1
5 3 1
Plain text

خروجی نمونه ۱🔗

3
4
9
1
Plain text

در شب اول، یک خوراک کباب با قیمت 11 و یک خوراک جوجه با قیمت 22، دو سیخ کباب و دو سیخ جوجه مورد نیاز را تأمین می‌کند.

در شب دوم، دو خوراک جوجه با قیمت 1×2=21 \times 2 = 2 و یک خوراک میکس با قیمت 22، یک سیخ کباب و پنج سیخ جوجه مورد نیاز را تأمین می‌کند.

برای شب سوم، کافی است که سه پرس میکس استاد سفارش دهد. 3×3=93 \times 3 = 9

در شب چهارم هم یک پرس میکس کفایت می‌کند که قیمت آن 11 است.