I - K-th Largest Triplet Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 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 が与えられます。

1\leq i,j,k\leq N を満たす整数 i,j,k の選び方 N^3 通りそれぞれに対して 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

Score : 500 points

Problem Statement

You are given three integer sequences of length N, namely A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N), and C=(C_1,C_2,\ldots,C_N), and an integer K.

For each of the N^3 choices of integers i,j,k (1\leq i,j,k\leq N), compute the value A_iB_j + B_jC_k + C_kA_i. Among all these values, find the K-th largest value.

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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

2 5
1 2
3 4
5 6

Sample Output 1

31

The N^3=8 values are computed as follows:

  • For (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
  • For (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
  • For (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
  • For (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
  • For (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
  • For (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
  • For (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
  • For (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

Sorting these values in descending order, we have (44,38,36,34,31,29,27,23), so the 5th largest value is 31.

Sample Input 2

3 10
100 100 100
100 100 100
100 100 100

Sample Output 2

30000

Sample Input 3

5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

Sample Output 3

689589940713840351