AT_arc037_c [ARC037C] 億マス計算

[problemUrl]: https://atcoder.jp/contests/arc037/tasks/arc037_c 高橋君は「$ 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 $) がスペース区切りで与えられる。

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

### 部分点 この問題には部分点が設定されている。 - $ 5 $ 点分のテストケースは $ 1 $ $ ≦ $ $ N $ $ ≦ $ $ 10 $ を満たす。 ### Sample Explanation 1 !\[\](http://arc037.contest.atcoder.jp/img/arc/037/ljlefijfewkjfwefk/C\_sample1.png) 高橋君が書き込んだ値を昇順に並べ替えると $ 6,\ 9,\ 10,\ 15 $ となり、小さい方から $ 3 $ 番目の値は $ 10 $ となる。 ### Sample Explanation 2 !\[\](http://arc037.contest.atcoder.jp/img/arc/037/ljlefijfewkjfwefk/C\_sample2.png) 高橋君が書き込んだ値を昇順に並べ替えると $ 1,\ 1,\ 2,\ 2,\ 2,\ 2,\ 2,\ 4,\ 4 $ となり、小さい方から $ 7 $ 番目の値は $ 2 $ となる。