给定两个序列A,B,长度分别为n,m。 设另有一个序列C中包含了A,B中的数两两相加的结果(C中共有n×m个数)。问C中第K小的数是多少。请注意重复的数需要计算多次。例如1,1,2,3中,最小和次小都是1,而3是第4小。
输入
输入的第一行包含三个整数n,m,K,相邻两个整数之间使用一个空格分隔。 第二行包含n个整数,分别表示A1,A2,...,An,相邻两个整数之间使用一个空格分隔。 第三行包含m个整数,分别表示B1,B2,...,Bm,相邻两个整数之间使用一个空格分隔。
输出
输出一行包含一个整数表示答案。
样例
| 标准输入 复制文本 |
3 4 5 1 3 4 2 3 5 6 |
| 标准输出 复制文本 |
6 |
提示
【评测用例规模与约定】 ·对于40%的评测用例,n,m≤5000,Ai,Bi≤1000; ·对于所有评测用例,1≤n,m≤100000,1≤Ai,Bi≤1000000000,1≤K≤n×m。