AT_abc391_f [ABC391F] K-th Largest Triplet

長さ $ 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 $

答えを出力せよ。

### Sample Explanation 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 $ です。 ### Constraints - $ 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 $ - 入力は全て整数