#P18149. Kth Sum

Kth Sum

Kth Sum

给定三个长度均为N的整数序列A、B、C。对于所有满足1≤i,j,k≤N的下标三元组,计算A_i+B_j+C_k,得到N³个和。

请输出其中第K小的和。不同下标三元组产生相同的数值时,这些和仍然分别计入排名。

输入格式

第一行包含两个整数N、K。

第二行包含N个整数A_1,…,A_N。

第三行包含N个整数B_1,…,B_N。

第四行包含N个整数C_1,…,C_N。

数据范围:

  • 1≤N≤50000。
  • 1≤K≤min(N³,10⁹)。
  • 0≤A_i,B_i,C_i≤10⁹。

数组不保证有序,也不保证元素互不相同。

输出格式

输出一个整数,表示第K小的和。

样例1

输入:

2 4
1 2
3 4
5 6

输出:

10

8个和从小到大依次为9,10,10,10,11,11,11,12,第4小为10。

样例2

输入:

10 40
11 9 13 12 15 11 11 2 11 17
3 1 10 2 12 18 9 11 11 15
14 9 4 14 16 9 20 2 1 18

输出:

14

样例3

输入:

1 1
1000000000
1000000000
1000000000

输出:

3000000000