EduBrick

k-я сумма пар

1000 мс · 256 МБ · всё или ничего

Даны массивы aa длины nn и bb длины mm. Рассмотрим все n⋅mn \cdot m сумм ai+bja_i + b_j и отсортируем их по неубыванию. Найдите kk-ю.

Формат ввода

В первой строке nn, mm и kk (1≤n,m≤1051 \le n, m \le 10^5, 1≤k≤n⋅m1 \le k \le n \cdot m). Во второй — nn чисел aia_i, в третьей — mm чисел bjb_j; все по модулю не больше 10910^9.

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

Выведите kk-ю по возрастанию сумму.

Примеры

ввод
1 1 1
5
7
вывод
12
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.