#P17719. [2026年福建省队集训]于二

[2026年福建省队集训]于二

题目描述

给定三个长度为 nn 的序列 a,b,ca,b,c。

通过从 a,b,ca,b,c 中分别取一个元素进行相加,这样可以生成 n3n^3 个数(可能相同),也就是说,通过如下方式生成一个可重集 SS:

for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
            S.insert(a[i]+b[j]+c[k]);

请回答 SS(生成的 n3n^3 个数形成的可重集)中的第 kk 小值。

输入格式

第一行两个整数 n,kn,k。

接下来一行 nn 个数,表示 aia_i。

接下来一行 nn 个数,表示 bib_i。

接下来一行 nn 个数,表示 cic_i。

输出格式

输出一个整数表示答案。

样例输入

3 6
10 1 7
4 2 6
6 8 5

样例输出

12

样例 2

见下发文件。满足测试点 77 的性质。

样例 3

见下发文件。满足测试点 1515 的性质。

数据范围

1≤n≤5×1041 \le n \le 5 \times 10^4,k≤min⁡(n3,109)k \le \min(n^3, 10^9),1≤ai,bi,ci≤1091 \le a_i, b_i, c_i \le 10^9。

测试点编号 特殊性质
1 n≤200n \le 200
2 ~ 3 n≤2000n \le 2000
4 ~ 6 k≤105k \le 10^5
7 ~ 14 a,b,ca, b, c 随机生成
15 ~ 20 无