← 返回题目列表

AtCoder · utpc2023_k

K. 第 K 次总和

中文机器翻译题面 查看原题

配点 : 100 点

問題文

长度 小于或等于 N 整数序列 给出 (A_1, A_2, \dots, A_N), (B_1, B_2, \dots, B_N), (C_1, C_2, \dots, C_N) 。 对于

1 \leq i \leq N, 1 \leq j \leq N, 1 \leq k \leq N 的整数 选择 i,j,k 如何选择 N^3 对于每条街道, 当求A_i + B_j + C_k 的值时, 找到第 K 个最小值。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 50000
  • 1 \leq K \leq \min\lbrace N^3, 10^9\rbrace
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_j \leq 10^9
  • 0 \leq C_k \leq 10^9

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
C_1 C_2 \dots C_N

出力

答案 请打印除以 1 行输出。


入力例 1

2 4
1 2
3 4
5 6

出力例 1

10

整数 i,j,k 如何选择 8 对应街道 A_i+B_j+C_k 的值为 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

出力例 2

14

入力例 3

1 1
1000000000
1000000000
1000000000

出力例 3

3000000000