AT_code_festival_2018_qualb_d Sushi Restaurant

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_d 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 $ $ M $ $ q $ $ x_1 $ $ p_1 $ $ x_2 $ $ p_2 $ $ x_3 $ $ p_3 $ $ : $ $ : $ $ x_M $ $ p_M $

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

### 制約 - $ N $ は $ 1 $ 以上 $ 2\ 000 $ 以下の整数 - $ M $ は $ 1 $ 以上 $ 2\ 000 $ 以下の整数 - $ 1\ \leq\ x_1\