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

Условие

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

Для этого необходимо перед этим пробить его грудь. Это место на Годзилле можно представить как прямоугольную сетку: есть n + 1 горизонтальных линий с y-координатами a₀ = 0,a₁,...,a_n и m + 1 вертикальных линий с x-координатами b₀ = 0,b₁,b₂,...,b_m. Они вместе образуют сеточное поле n × m с клетками разного размера. Исследователи собираются разработать специальные анти-Годзилла снаряды мощности p, чтобы расстрелять ими каждую клетку на груди Годзиллы. Клетка размера h × w будет разрушена снарядом мощности p, если h ⋅ w ≤ p, иначе клетка выдержит удар и не разрушится.

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

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

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

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

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

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

Ограничения

1 ≤ n,m ≤ 10⁵, 1 ≤ k ≤ n ⋅ m

0 ≤ a₁ < …  < a_n ≤ 10⁹

0 ≤ b₁ < …  < b_m ≤ 10⁹

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

4 5 7
2 5 6 8
3 5 6 10 12

3

3 5 14
1 4 5
4 6 8 10 13

9

Разбор

Первым делом, берём разности исходного массива, так как нас интересуют только длины сторон ячеек:

for(int i=n; i>0; —i) a[i] = a[i] - a[i-1];

for(int i=m; i>0; —i) b[i] = b[i] - b[i-1];

Далее заметим, что порядок каждого из массивов неважен — множество ячеек не меняется от этого. Поэтому можем отсортировать оба массива по неубыванию:

sort(a.begin(), a.end());

sort(b.begin(), b.end());

На это идет O(nlog n + mlog m) операций.

Очевидно, что существует минимальное p′ такое, что для любых p, меньших p′, Годзиллу не получится победить, а для любых p ≥ p′ получится победить. Значит, можем искать этот p′ через бинарный поиск по p. Осталось понять, как быстро считать количество поражаемых ячеек для заданного p. Количество ячеек может быть очень большим: n ⋅ m ≤ 10¹⁰. Будем идти строка за строкой и двигать справа налево указатель j, который будет указывать на последний элемент строки такой, что его поражает снаряд p. Главное наблюдение: при переходе с строки i на i + 1, указатель j может двигаться только налево. Поэтому в итоге, i пробегает от 1 до n, а j — от m до t ≥ 1.