AT_tkppc4_1_j school competition 2

[problemUrl]: https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_j さて、Paken島の人々は、学校対抗戦に各校 $ 2 $ 人しか出られないことは問題であると考え学校対抗戦のルールを改めることにしました。([school competition 1](https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i)) anmichi校に通う $ N $ 人の生徒のうち $ i $ 番目の人のレーティングは $ A_i $、sanada校に通う $ M $ 人の生徒のうち $ j $ 番目の人のレーティングは $ B_j $ です。 ここで、以下のようなルールがあります。 - 両校ともAチームとBチームの $ 2 $ チームに分かれ、anmichi校のAチームとsanada校のAチーム、anmichi校のBチームとsanada校のBチームがそれぞれ対決する。 - 両校ともに、Aチームに所属する生徒のレーティングの総和は、Bチームに所属する生徒のレーティングの総和よりも**真に**大きくなければならない。 - $ 2 $ チームが対決するとき、チームに所属する生徒のレーティングの総和が大きいチームが勝つ。また、レーティングの総和が等しい場合は引き分けとなる。 - どのチームにも $ 1 $ 人以上の生徒がいなくてはならない。 - AチームとBチーム両方に所属する生徒がいてはならず、AチームとBチームどちらにも所属しない生徒がいてもならない。 anmichi校は、sanada校にAチームBチーム両方で勝ちたいです。そこで、最善にチーム分けをしたときに両チームとも勝てる確率を求めてください。 なお、sanada校のチーム分けは、上の条件を満たす分け方をすべて挙げた上でその中から等確率で選ぶものとします。 ただし、ある $ 2 $ つのsanada校のチーム分けが異なるとは、一方の分け方で所属するチームともう一方の分け方で所属するチームが異なる生徒が存在することを指します。 また、anmichi 校、sanada 校の両校において、$ 1 $ 通り以上のチーム分けの組合せが存在することが保証されています。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ > $ A_1 $ $ A_2 $ $ \ldots $ $ A_{N-1} $ $ A_N $ > $ B_1 $ $ B_2 $ $ \ldots $ $ B_{M-1} $ $ B_M $

anmichi校が最適なチーム分けを行なったとき、anmichi校がsanada校に両チームとも勝つ確率を $ 1 $ 行に出力してください。 絶対誤差または相対誤差が $ 10^{-6} $ 未満の場合正解となります。 ただし、自分チームと相手チームのレーティングの総和が同じ場合は勝ちにならないことに注意してください。

### 制約 - 入力は全て整数である。 - $ 2\leq\ N,M\ \leq\ 20 $ - $ 0\ \leq\ A_i,B_i\ \leq\ 10^{9} $ - anmichi 校, sanada 校の両校において、条件を満たすチーム分けが $ 1 $ 通り以上存在する。 ### Sample Explanation 1 anmichi校はAチームには $ 1 $ 番目の生徒、Bチームには $ 2 $ 番目の生徒が出ます。 また、sanada校はAチームには $ 1 $ 番目の人、Bチームには $ 2 $ 番目の人が出ます。 この場合、Bチームは勝てますがAチームは勝てないので、AチームBチーム両方で勝つ確率は $ 0 $ です。 ### Sample Explanation 2 anmichi校はAチームには2番目の人、Bチームには1番目の人が出ます。 また、sanada校のチーム分けの仕方は以下の $ 2 $ 通り存在します。 - Aチームには $ 1,\ 3 $ 番目の人、Bチームには $ 2 $ 番目の人が出る。 - Aチームには $ 2,\ 3 $ 番目の人、Bチームには $ 1 $ 番目の人が出る。 どちらの場合でもanmichi校は、AチームBチーム両方で勝てるので、確率は $ 1 $ です。 sanada校の分け方において、同じレーティングの人を区別すること、また、同じレーティングのチーム分けを区別することに注意してください。