配点: $700$ 点

問題文

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$.

入力

入力は以下の形式で標準入力から与えられる.

$N$ $M$ $q$ $x_1$ $p_1$ $x_2$ $p_2$ $x_3$ $p_3$ $:$ $:$ $x_M$ $p_M$

出力

不適合度の期待値の達成可能な最小値を出力しなさい.
ジャッジの解からの絶対誤差または相対誤差が $\\pm 0.0001$ 以内であれば正解とみなされる.

入力例 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$ となり, これが達成可能な最小値である.