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

حل سؤال در بانک سؤالات