- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بیژن یک کیک مستطیلی برای تولد کوئرا خریداری کرده است و کیک را با تعدادی برش افقی و عمودی موازی اضلاع مستطیل، به تکه‌های مستطیلی تقسیم کرده است.
منیژه با تعدادی از دوستان خود به جشن آمده است. او برای دوستان خود بزرگترین تکه‌ها را جدا کرده و به هر نفر یک تکه کیک می‌دهد. سپس برای خودش بزرگترین تکه کیک باقی مانده را برمی‌دارد.
می‌دانیم عرض کیک با برش‌های افقی، و طول کیک با برش‌های عمودی به تعدادی قسمت تقسیم شده است. تعدادی سناریو داریم. در هر سناریو، منیژه در ابتدا تعداد افراد گروه خود که شامل دوستانش و خودش است را به شما می‌گوید. سپس تعداد قسمت‌هایی که عرض و طول کیک تقسیم شده‌اند و طول هر قسمت را می‌گوید و از شما می‌خواهد به او بگویید مساحت تکه کیک او چقدر خواهد بود.
ورودی
در ابتدا در خط اول عدد $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
ارسال پاسخ برای این سؤال