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

---

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

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

ورودی

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

\[1 \le t \le 100,000\]

خط اول توضیحات شام \(i\)ام دو عدد \(k_i\) و \(j_i\) می‌آیند که به ترتیب از چپ حداقل تعداد کباب‌ها و جوجه‌هایی که استاد باید آن شب بخرد را نشان می‌دهند.

\[0 \le k_i, j_i \le 1,000,000\]

در سطر بعد سه عدد \(Kabaab_i\)، \(Joojeh_i\) و \(Mix_i\) می‌آید که به‌ترتیب از چپ نشان‌گر قیمت «خوراک کباب»، «خوراک جوجه» و «خوراک میکس» است.

\[1 \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

خروجی نمونه ۱

3
4
9
1

در شب اول، یک خوراک کباب با قیمت \(1\) و یک خوراک جوجه با قیمت \(2\)، دو سیخ کباب و دو سیخ جوجه مورد نیاز را تأمین می‌کند.

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

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

در شب چهارم هم یک پرس میکس کفایت می‌کند که قیمت آن \(1\) است.