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

بیژن یک کیک مستطیلی برای تولد کوئرا خریداری کرده است و کیک را با تعدادی برش افقی و عمودی موازی اضلاع مستطیل، به تکه‌های مستطیلی تقسیم کرده است.

منیژه با تعدادی از دوستان خود به جشن آمده است. او برای دوستان خود بزرگترین تکه‌ها را جدا کرده و به هر نفر یک تکه کیک می‌دهد. سپس برای خودش بزرگترین تکه‌ کیک باقی مانده را برمی‌دارد.

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

ورودی

در ابتدا در خط اول عدد $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