题目描述

九度OJ 1534

给定两个升序整型数组$\red{A}$和$\red{B}$。将$\red{A}$和$\red{B}$中的元素两两相加可以得到数组$\red{C}$。譬如，$\red{A}$为$\red{[1，2]}$，$\red{B}$为$\red{[3，4]}$，那么由$\red{A}$和$\red{B}$中的元素两两相加得到的数组$\red{C}$为$\red{[4，5，5，6]}$。现在给你数组$\red{A}$和$\red{B}$，求由$\red{A}$和$\red{B}$两两相加得到的数组$\red{C}$中，第$\red{k}$小的数字是多少？”

输入格式

输入可能包含多组测试数据。

对于每组测试数据，输入的第一行为三个整数$\red{m，n，k（1≤m，n≤100 000， 1≤k≤n×m）}$，其中$\red{m}$和$\red{n}$代表将要输入数组$\red{A}$和$\red{B}$的长度。

紧接着两行，分别有$\red{m}$和$\red{n}$个数，代表数组$\red{A}$和$\red{B}$中的元素。数组元素范围为$\red{[0，1×10^9]}$。

输出格式

对应每个测试案例，输出由$\red{A}$和$\red{B}$中元素两两相加得到的数组$\red{C}$中第$\red{k}$小的数字。

样例

输入样例

2 2 3

1 2

3 4

3 3 4

1 2 7

3 4 5

输出样例

5

6