問題

Moja くんはネット通販で mm 個の商品を注文しました。また、Moja くんのお母さん(以下、お母さんという)はネット通販で nn 個の商品を注文しました。二人とも、商品の配達を楽しみに待っています。

Moja くんが注文した商品の重量はそれぞれ a1,a2, ,ama_1, a_2, \ \ldots, a_m で、お母さんが注文した商品の重量はそれぞれ b1,b2, ,bnb_1, b_2, \ \ldots, b_n です。

Moja くんの家に重量 MM の商品が配達されると、お母さんは宛先を確認せずに max(0,max1in(1Mbibi))\max \left(0, \displaystyle\max_{1 \leq i \leq n} \left(1 - \frac{\lvert M - b_i \rvert}{b_i} \right) \right) の確率でその商品を開封してしまいます。

Moja くんに宛てられた mm 個の商品のうち、お母さんが開封してしまう商品の個数の期待値を求めてください。ただし、お母さんは忘れっぽいため既に届いた自分宛ての商品についても、その商品に近い重量の商品が家に届いた時にそれを上記の確率で開封してしまいます。

制約

  • 1m500,0001 \leq m \leq 500,000
  • 1n500,0001 \leq n \leq 500,000
  • 1ai500,000(for1im)1 \leq a_i \leq 500,000 \hspace{0.3em} \left(\mathrm{for} \hspace{0.3em} 1 \leq i \leq m \right)
  • 1bi500,000(for1in)1 \leq b_i \leq 500,000 \hspace{0.3em} \left(\mathrm{for} \hspace{0.3em} 1 \leq i \leq n \right)
  • 入力は全て整数

入力

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

m nm \ n\\ a1 a2  ama_1 \ a_2 \ \ldots \ a_m\\ b1 b2  bnb_1 \ b_2 \ \ldots \ b_n\\

出力

Moja くんに宛てられた mm 個の商品のうち、お母さんが開封してしまう商品の個数の期待値を標準出力に出力してください。

MojaCoder の誤差ジャッジで想定出力と近いと判断された値は正解となります。(想定出力では小数第 20 位までを出力しています)

サンプル

入力例1
1 4
5
2 8 6 4
出力例1
0.8333333333

重量が 55 の Moja くんの商品をお母さんが開封してしまう確率は

max(0,max(1522,1588,1566,1544))\hspace{1em} \max \left(0,\, \displaystyle\max \left(1 - \frac{\lvert 5 - \textcolor{orange}{2} \rvert}{\textcolor{orange}{2}},\, 1 - \frac{\lvert 5 - \textcolor{orange}{8} \rvert}{\textcolor{orange}{8}},\, 1 - \frac{\lvert 5 - \textcolor{orange}{6} \rvert}{\textcolor{orange}{6}},\, 1 - \frac{\lvert 5 - \textcolor{orange}{4} \rvert}{\textcolor{orange}{4}} \right) \right)

=max(0,132,138,116,114)= \displaystyle\max \left(0,\, \hspace{5em} 1 - \frac{3}{2},\, \hspace{2.25em} 1 - \frac{3}{8},\, \hspace{2.25em} 1 - \frac{1}{6},\, \hspace{2.25em} 1 - \frac{1}{4} \right)

=max(0, 12, 58, 56, 34)= \displaystyle\max \left(0,\ - \frac{1}{2},\ \frac{5}{8},\ \frac{5}{6},\ \frac{3}{4} \right)

=56(=0.833333)= \displaystyle\frac{5}{6} \hspace{0.5em} \left( = 0.833333 \ldots \right)

です。


入力例2
3 1
3 3 3
3
出力例2
3.0000000000

お母さんは Moja くんの商品を全て開封してしまいます。Moja くんはコンビニ受け取りを利用するようになるでしょう。


入力例3
3 2
100000 300000 500000
1 3
出力例3
0.0000000000

Moja くんが注文した商品はお母さんが注文した商品と比べて十分重いようです。

提出


Go (1.21)