問題
Moja くんはネット通販で m 個の商品を注文しました。また、Moja くんのお母さん(以下、お母さんという)はネット通販で n 個の商品を注文しました。二人とも、商品の配達を楽しみに待っています。
Moja くんが注文した商品の重量はそれぞれ a1,a2, …,am で、お母さんが注文した商品の重量はそれぞれ b1,b2, …,bn です。
Moja くんの家に重量 M の商品が配達されると、お母さんは宛先を確認せずに max(0,1≤i≤nmax(1−bi∣M−bi∣)) の確率でその商品を開封してしまいます。
Moja くんに宛てられた m 個の商品のうち、お母さんが開封してしまう商品の個数の期待値を求めてください。ただし、お母さんは忘れっぽいため既に届いた自分宛ての商品についても、その商品に近い重量の商品が家に届いた時にそれを上記の確率で開封してしまいます。
制約
- 1≤m≤500,000
- 1≤n≤500,000
- 1≤ai≤500,000(for1≤i≤m)
- 1≤bi≤500,000(for1≤i≤n)
- 入力は全て整数
入力
入力は標準入力から以下の形式で与えられます。
出力
Moja くんに宛てられた m 個の商品のうち、お母さんが開封してしまう商品の個数の期待値を標準出力に出力してください。
MojaCoder の誤差ジャッジで想定出力と近いと判断された値は正解となります。(想定出力では小数第 20 位までを出力しています)
サンプル
重量が 5 の Moja くんの商品をお母さんが開封してしまう確率は
max(0,max(1−2∣5−2∣,1−8∣5−8∣,1−6∣5−6∣,1−4∣5−4∣))
=max(0,1−23,1−83,1−61,1−41)
=max(0, −21, 85, 65, 43)
=65(=0.833333…)
です。
お母さんは Moja くんの商品を全て開封してしまいます。Moja くんはコンビニ受け取りを利用するようになるでしょう。
入力例3
3 2
100000 300000 500000
1 3
Moja くんが注文した商品はお母さんが注文した商品と比べて十分重いようです。