- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک ربات داریم که در مبدا مختصات قرار دارد! هر بار ربات یک دستور می‌خواند و یک واحد بر روی صفحه مختصات دوبعدی طبق آن حرکت می‌کند. ۴ دستور ما «بالا»، «پایین»، «چپ» و «راست» هستند.
حال به شما تعدادی دستور داده می‌شود و شما باید همه آن‌ها را به ربات بدهید. اما می‌توانید حداکثر $k$ عملیات انجام دهید. در یک عملیات می‌توانید یکی از دستورها را به یک دستور دیگر تبدیل کنید به شرطی که جهت مخالف دستور فعلی نباشد.
به عبارت دیگر در یک عملیات نمی‌توانیم «بالا» و «پایین» را به هم و «چپ» و «راست» تبدیل کرد ولی بقیه تبدیل‌ها مجاز هستند. توجه کنید یک دستور را به تعداد دلخواه می‌توانید تغییر دهید.
برای مثال اگر دو دستور «بالا» + «چپ» را داشته باشیم. می‌توانیم با یک عملیات آن را به «چپ» + «چپ» یا «راست» + «چپ» یا «بالا» + «بالا» یا «بالا» + «پایین» تبدیل کرد اما نمی‌توانیم آن را به «پایین» + «چپ» یا «بالا» + «راست» تبدیل کرد.
حال می‌خواهیم بدانیم به ازای سناریوهای مختلف و مستقل هربار ربات حداکثر چه مقدار می‌تواند از مبدا دور شود!
ورودی
در سطر اول ورودی $t$ یا تعداد سناریوهای مختلف می‌آید.
$$ 1 \le t \le 100 , 000 $$
در $t$ خط بعد در هر خط ۵ عدد طبیعی می‌آید. عدد اول $R$ نشانگر تعداد دستورهای راست، عدد دوم $U$ تعداد دستورهای بالا، عدد سوم $L$ تعداد دستورهای چپ و عدد چهارم $D$ تعداد دستورهای پایین است. عددد آخر $k$ هم حداکثر تعداد تغییرهای مجاز را نشان می‌دهد.
$$ 0 \le R, U, L, D, k \le 10^9$$
خروجی
در $t$ سطر خروجی در هر سطر یک عدد صحیح برابر با مجذور بیشینه فاصله ممکن ربات تا مبدا را خروجی دهید.
مثال
ورودی نمونه ۱
5
1 0 1 0 1
1 2 3 4 2
5 0 4 0 4
4 1 1 5 3
899565959 554564564 149637852 76162365 1000000000
خروجی نمونه ۱
2
32
41
65
2822167291196947600
در مثال اول در ابتدا یک «راست» و یک «چپ» داریم که اگر با یک تغییر «چپ» را به «بالا» عوض کنیم آنگاه یک «راست» و یک «بالا» خواهیم داشت و مجذور فاصله ما ۲ خواهد بود. با توجه به اینکه مستقیماً نمی‌توان «چپ» را تبدیل به «راست» کرد به فاصله دورتری از مبدا با یک عملیات نمی‌توان رسید.
در مثال دوم اگر با دو عملیات دو «بالا» را به دو «چپ» تبدیل کنیم آنگاه ۴ «پایین»، ۵ «چپ» و ۱ «راست» خواهیم داشت. پس ربات در نقطه $(-4,4)$ قرار خواهد گرفت و مجذور فاصله آن ۳۲ خواهد بود.
در مثال سوم اگر با ۴ عملیات هر ۴ «چپ» را به ۴ «پایین» تبدیل کنیم آنگاه ربات در نقطه $(5,-4)$ با مجذور فاصله ۴۱ از مبدا قرار خواهد گرفت.
در مثال چهارم اگر با دو عملیات تنها «بالا» را به «پایین» تبدیل کنیم (یکبار «بالا» را به «راست» و بار دیگر «راست» را به «پایین») و با یک عملیات دیگر تنها «چپ» را به «پایین» تبدیل کنیم, آنگاه ۷ «پایین» و ۴ «راست» خواهیم داشت و فاصله ما از مبدا $\sqrt {65}$ خواهد بود.
ارسال پاسخ برای این سؤال