题目描述

给定两个长度分别为 $n$ 和 $m$ 的正整数序列 $A$ 和 $B$。将 $A$ 中的每个元素与 $B$ 中的每个元素相加，可以得到 $n\times m$ 个和，组成序列 $C$（允许重复值多次出现）。请找出 $C$ 中第 $K$ 小的值。

例如 $A=\{1,2\}$，$B=\{3,4\}$，则 $C=\{4,5,5,6\}$，其中第 $1$ 小为 $4$，第 $2$ 小为 $5$，第 $4$ 小为 $6$。

输入格式

第一行包含三个正整数 $n,m,K$，用空格分隔。

第二行包含 $n$ 个正整数 $A_1,A_2,\ldots,A_n$，用空格分隔。

第三行包含 $m$ 个正整数 $B_1,B_2,\ldots,B_m$，用空格分隔。

输出格式

输出一行一个整数，表示第 $K$ 小的配对和。

样例

3 4 5
1 3 4
2 3 5 6

6

提示

对于 $40\%$ 的数据，$n,m\le 5000$，$A_i,B_i\le 1000$。

对于 $100\%$ 的数据，$1\le n,m\le 10^5$，$1\le A_i,B_i\le 10^9$，$1\le K\le n\times m$。

提示：可以对答案进行二分搜索，对 $B$ 排序后利用 upper_bound 统计不超过某个值的配对数。