Задача L. Минимальная мощность

Автор:Dulustan Nikiforov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Все любят фильмы про Годзиллу. Прямо как в этих фильмах, Годзилла внезапно появился и уже уничтожил Японию! Чтобы предотвратить дальнейшие разрушения, лидеры мировых держав собрали команду элитных исследователей. Они выяснили, что у Годзиллы есть сердце, работающее как атомный генератор. Чтобы победить Годзиллу, необходимо заморозить его сердце.

Для этого необходимо перед этим пробить его грудь. Это место на Годзилле можно представить как прямоугольную сетку: есть n + 1 горизонтальных линий с y-координатами a0 = 0,a1,...,an и m + 1 вертикальных линий с x-координатами b0 = 0,b1,b2,...,bm. Они вместе образуют сеточное поле n × m с клетками разного размера. Исследователи собираются разработать специальные анти-Годзилла снаряды мощности p, чтобы расстрелять ими каждую клетку на груди Годзиллы. Клетка размера h × w будет разрушена снарядом мощности p, если h ⋅ w ≤ p, иначе клетка выдержит удар и не разрушится.

Путем невероятно умных расчетов, исследователи смогли выяснить, что необходимо разрушить хотя бы k клеток, чтобы грудная пластина Годзиллы выпала и обнажила его сердце. Так как разработка более мощных снарядов занимает большее время, а человеческие жизни теряются каждую минуту, надо найти минимальную мощность снаряда для победы над Годзиллой.

К сожалению, в команде не оказалось способных программистов, чтобы вычислить оптимальную мощность p (целое число) снаряда. Сможете ли вы это сделать, чтобы спасти мир (точнее, то, что от него осталось)?

Формат входных данных

Первой строкой даны три целых числа: n,m,k. Во второй строке даны n целых чисел ai. В третьей строке даны m целых чисел bi.

Формат выходных данных

Выведите единственное целое число p — минимальная мощность снарядов, нужное для победы над Годзиллой.

Ограничения

1 ≤ n,m ≤ 105, 1 ≤ k ≤ n ⋅ m

0 ≤ a1 < … an ≤ 109

0 ≤ b1 < … bm ≤ 109

Примеры тестов

Стандартный вход Стандартный выход
1
4 5 7
2 5 6 8
3 5 6 10 12
3
2
3 5 14
1 4 5
4 6 8 10 13
9

0.065s 0.010s 13