#LQ1487. 第K小的和

第K小的和

问题描述

给定两个序列 A,BA,B,长度分别为 n,mn,m

设另有一个序列 CC 中包含了 A,BA,B 中的数两两相加的结果 (CC 中共有 n×mn×m 个数)。问 CC 中第 KK 小的数是多少。请注意重复的数需要计算多次。例如 1,1,2,31,1,2,3 中,最小和次小都是 11,而 33 是第 44 小。

输入格式

输入的第一行包含三个整数 n,m,Kn,m,K,相邻两个整数之间使用一个空格分隔。

第二行包含 nn 个整数,分别表示 A1,A2,,AnA_1,A_2,…,A_n​,相邻两个整数之间使用一个空格分隔。

第三行包含 mm 个整数,分别表示 B1,B2,,BmB_1,B_2,…,B_m​,相邻两个整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例

3 4 5
1 3 4
2 3 5 6
6

评测用例规模与约定

对于 40%40\% 的评测用例,n,m5000n,m≤5000Ai,Bi1000A_i,B_i≤1000;

对于所有评测用例,1n,m1051≤n,m≤10^51Ai,Bi1091≤A_i,B_i≤10^91Kn×m1≤K≤n×m