AT_abc391_f [ABC391F] K-th Largest Triplet

[problemUrl]: https://atcoder.jp/contests/abc391/tasks/abc391_f 给定长度为 $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$。 对于所有满足 $1 \leq i,j,k \leq N$ 的整数三元组 $(i,j,k)$ 的 $N^3$ 种选择方式，计算 $A_iB_j + B_jC_k + C_kA_i$ 的值。请输出这些值中从大到小第 $K$ 个的值。

输入通过标准输入按以下格式给出： > $N$ $K$ > $A_1$ $A_2$ $\ldots$ $A_N$ > $B_1$ $B_2$ $\ldots$ $B_N$ > $C_1$ $C_2$ $\ldots$ $C_N$

输出答案。

### 约束条件 - $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$ - 输入均为整数 ### 样例解释 1 $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$。 翻译由 DeepSeek R1 完成