C - 億マス計算 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋君は「N^2マス計算」で計算力をつけることにした。「N^2マス計算」は N 行 N 列の表を用意して行う。 i 行目の左端のマスのさらに左には数 a_i が書かれており、 j 列目の上端のマスのさらに上には数 b_j が書かれている。高橋君はこの表の i 行 j 列目 に a_i × b_j の値を計算して書き込む。

すぐに解き終わってしまい退屈したので、高橋君は自分が書き込んだ N^2 個の値を昇順に並べ替えることにした。並べ替えた結果小さい方から K 番目 (1 番から数える) に位置する値を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1 a_2 .. a_N
b_1 b_2 .. b_N
  • 1 行目には、表の行数および列数 N (1 ≦ N ≦ 30000) と求めるべき値の並べ替え後の位置 K (1 ≦ K ≦ N^2) がスペース区切りで与えられる。
  • 2 行目には、表の各行 i (1 ≦ i ≦ N) について、その行の左端のマスよりさらに左に書かれた数 a_i (1 ≦ a_i ≦ 10^9) がスペース区切りで与えられる。
  • 3 行目には、表の各列 j (1 ≦ j ≦ N) について、その列の上端のマスよりさらに上に書かれた数 b_j (1 ≦ b_j ≦ 10^9) がスペース区切りで与えられる。

部分点

この問題には部分点が設定されている。

  • 5 点分のテストケースは 1 ≦ N ≦ 10 を満たす。

出力

標準出力に、高橋君が表に書き込んだ N^2 個の値を昇順に並べ替えたとき小さい方から K 番目 (1 番から数える) に位置する値を出力し、末尾で改行せよ。

入力例1

2 3
2 3
3 5

出力例1

10

高橋君が書き込んだ値を昇順に並べ替えると 6, 9, 10, 15 となり、小さい方から 3 番目の値は 10 となる。

入力例2

3 7
1 2 1
2 1 2

出力例2

2

高橋君が書き込んだ値を昇順に並べ替えると 1, 1, 2, 2, 2, 2, 2, 4, 4 となり、小さい方から 7 番目の値は 2 となる。

入力例3

4 8
701687787 500872619 516391519 599949380
458299111 633119409 377269575 717229869

出力例3

317112176525562171