分数: 500 点
问题陈述
给定三个长度的整数序列 N,即 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N),和 C=(C_1,C_2,\ldots,C_N),和一个整数 K.
对于每个 N^3 整数的选择 i,j,k (1\leq i,j,k\leq N),计算值 A_iB_j + B_jC_k + C_kA_i。在所有这些值中,找到 K- 第一个最大值。
约束
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq \min(N^3,5\times 10^5)
- 1\leq A_i,B_i,C_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N C_1 C_2 \ldots C_N
输出
打印答案。
示例输入 1
2 5 1 2 3 4 5 6
示例输出 1
31
的 树的 N^3=8 值计算如下:
- 对于 (i,j,k)=(1,1,1): A_1B_1+B_1C_1+C_1A_1=1\times 3+3\times 5+5\times 1=23
- 对于 (i,j,k)=(1,1,2): A_1B_1+B_1C_2+C_2A_1=1\times 3+3\times 6+6\times 1=27
- 对于 (i,j,k)=(1,2,1): A_1B_2+B_2C_1+C_1A_1=1\times 4+4\times 5+5\times 1=29
- 对于 (i,j,k)=(1,2,2): A_1B_2+B_2C_2+C_2A_1=1\times 4+4\times 6+6\times 1=34
- 对于 (i,j,k)=(2,1,1): A_2B_1+B_1C_1+C_1A_2=2\times 3+3\times 5+5\times 2=31
- 对于 (i,j,k)=(2,1,2): A_2B_1+B_1C_2+C_2A_2=2\times 3+3\times 6+6\times 2=36
- 对于 (i,j,k)=(2,2,1): A_2B_2+B_2C_1+C_1A_2=2\times 4+4\times 5+5\times 2=38
- 对于 (i,j,k)=(2,2,2): A_2B_2+B_2C_2+C_2A_2=2\times 4+4\times 6+6\times 2=44
按降序对这些值进行排序,我们有 (44,38,36,34,31,29,27,23),所以第 5 个最大值是 31.
示例输入 2
3 10 100 100 100 100 100 100 100 100 100
示例输出 2
30000
示例输入 3
5 54 800516877 573289179 26509423 168629803 696409999 656737335 915059758 201458890 931198638 185928366 140174496 254538849 830992027 305186313 322164559
示例输出 3
689589940713840351