長い長い数列 (paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

数列 A = (A_1, A_2, ..., A_n) と数列 B = (B_1, B_2, ..., B_m) が与えられます。
これらの数列を用いて、n 行 m 列のマス目に数を書き込むことを考えます。具体的には、i 行 j 列目(1 ≦ i ≦ n, 1 ≦ j ≦ m) に | A_i - B_j | を書き込みます。表に書き込まれる数は全部で n*m 個ありますが、それらを小さいほうから並べたとき k 番目にくる値を求めてください。

入力される値

n
A_1 A_2 ... A_n
m
B_1 B_2 ... B_m
k

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

表に書き込まれる数を小さいほうから並べたときに k 番目にくる値を出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数

・ 1 ≦ n ≦ 30,000

・ -10^8 ≦ A_i ≦ 10^8 (1 ≦ i ≦ n)

・ 1 ≦ m ≦ 30,000

・ -10^8 ≦ B_i ≦ 10^8 (1 ≦ i ≦ m)

・ 1 ≦ k ≦ n*m

入力例1: 5
0 1 2 3 4
4
-3 -1 1 3
12

出力例1: 3

問題一覧へ戻る