- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بیژن یک کیک مستطیلی برای تولد کوئرا خریداری کرده است و کیک را با تعدادی برش افقی و عمودی موازی اضلاع مستطیل، به تکههای مستطیلی تقسیم کرده است.
منیژه با تعدادی از دوستان خود به جشن آمده است. او برای دوستان خود بزرگترین تکهها را جدا کرده و به هر نفر یک تکه کیک میدهد. سپس برای خودش بزرگترین تکه کیک باقی مانده را برمیدارد.
میدانیم عرض کیک با برشهای افقی، و طول کیک با برشهای عمودی به تعدادی قسمت تقسیم شده است. تعدادی سناریو داریم. در هر سناریو، منیژه در ابتدا تعداد افراد گروه خود که شامل دوستانش و خودش است را به شما میگوید. سپس تعداد قسمتهایی که عرض و طول کیک تقسیم شدهاند و طول هر قسمت را میگوید و از شما میخواهد به او بگویید مساحت تکه کیک او چقدر خواهد بود.
ورودی
در ابتدا در خط اول عدد \(q\)، که نشانگر تعداد سناریوها است داده میشود.
\[1 \leq q \leq 100 \, 000\]
هر سناریو در ۳ خط ورودی داده می،شود. در ابتدا در خط اول هر سناریو، اعداد \(n\) و \(m\) و \(k\) ورودی داده میشوند که به ترتیب تعداد قسمتهای تقسیم شده عرض و طول کیک و عدد \(k\) نیز جمعیت گروه منیژه و دوستانش را مشخص میکنند.
\[1 \leq n, m \leq 100\, 000, \quad \quad 1 \leq k \leq mn\]
سپس در خط دوم به ترتیب \(n\) عدد، که طول قسمتهایی که عرض کیک برش داده شده است را مشخص میکند ورودی داده میشوند.
\[1 \leq h_i \leq 10^9\]
و در خط سوم \(m\) عدد، که طول قسمتهایی که طول مستطیل کیک برش داده شده است، داده میشود.
\[1 \leq v_i \leq 10^9\]
تضمین میشود که مجموع \(n + m\) روی همهی سناریوها حداکثر ۱۰۰،۰۰۰ باشد.
خروجی
در \(q\) خط، و در هر خط یک عدد که نشانگر مساحت \(k\) امین بزرگترین تکه کیک آن سناریو است را خروجی دهید.
مثالها
ورودی نمونه ۱
3
1 2 1
4
3 1
5 1 5
6 10 10 6 10
10
4 9 8
2 2 1 1
3 9 3 7 9 5 9 1 1
خروجی نمونه ۱
12
60
14