問題文

CODE FESTIVAL 2018 本戦の参加者は N 人である. これから, 彼らは夕食で寿司を食べる.

それぞれの参加者は 空腹度 という整数の値を持つ. この値は, それぞれの参加者について独立に, 以下のように定まる.

• 確率 \frac{p_1}{q} で空腹度 x_1, 確率 \frac{p_2}{q} で空腹度 x_2, ... , 確率 \frac{p_M}{q} で空腹度 x_M.

あなたは寿司職人である. 厨房に N 枚の皿があり, あなたはそれぞれの皿に寿司を 1 個以上乗せる. 皿に乗せられる寿司の数に制限はなく, 皿ごとに異なる個数の寿司を乗せてもよい.

そして, これら N 枚の皿が参加者たちの座るテーブルに運ばれ, 彼らは皿をそれぞれ 1 枚取る.
空腹度 x の参加者が y 個の寿司の乗った皿を取ると, その参加者の 不満度 は |x - y| となる.
参加者たちは彼ら自身の空腹度を把握しており, 彼らは全員の不満度の合計が最小となるように皿を取る. このときの全員の不満度の合計を 不適合度 と呼ぶ.

あなたは, 不適合度の期待値が最小となるように皿に寿司を乗せたい. このように皿に寿司を乗せたときの不適合度の期待値を求めよ.

制約

• N は 1 以上 2 \ 000 以下の整数
• M は 1 以上 2 \ 000 以下の整数
• 1 \leq x_1 < x_2 < x_3 < ... < x_M \leq 1 \ 000 \ 000.
• p_i \ (1 \leq i \leq M) は, 1 以上 1 \ 000 \ 000 以下の整数
• q は 1 以上 1 \ 000 \ 000 以下の整数
• p_1 + p_2 + p_3 + ... + p_M = q.

入力例 1

1 3 100
1 30
3 20
9 50

出力例 1

3.6000000000

この場合, 参加者は 1 人であり, 彼の空腹度は確率 30/100 = 0.3 で 1, 確率 20/100 = 0.2 で 3, 確率 50/100 = 0.5 で 9 となる.
1 枚の皿に 6 個の寿司を乗せることを考える. 唯一の参加者がこの皿を取り, 不適合度の期待値, すなわちこの参加者の不満度の期待値は |1-6| \times 0.3 + |3-6| \times 0.2 + |9-6| \times 0.5 = 3.6 となる.
これが達成可能な最小値である.

入力例 2

2 3 10
1 3
3 2
9 5

出力例 2

4.1600000000

この場合, 参加者は 2 人であり, 彼らを A, B と呼ぶことにする. 彼らの空腹度の確率分布はそれぞれ入力例 1 での参加者のそれと同じである. また, 2 枚の皿を皿 1, 皿 2 と呼ぶことにする.
皿 1 に 9 個, 皿 2 に 1 個の寿司を置くことを考える.
例えば, 確率 30/100 × 20/100 で A, B の空腹度がそれぞれ 1, 3 となる。このとき, A が皿 2, B が皿 1 を取ることで二人の不満度の合計が |1-1| + |3-9| = 6 となって最小化されるため, 不適合度は 6 である.
その他の場合についても同様に計算することで, 寿司をこのように置いたときの不適合度の期待値が 4.16 であることがわかる.
これが達成可能な最小値である.

入力例 3

3 2 2
111111 1
999999 1

出力例 3

666665.9999999997

1 枚目の皿に 111 \ 111 個, 2 枚目の皿に 999 \ 999 個, 3 枚目の皿に 555 \ 555 個の寿司を置くと, 不適合度の期待値は 666 \ 666 となり, これが達成可能な最小値である.