AT_code_festival_2018_qualb_d Sushi Restaurant

在 CODE FESTIVAL 2018 决赛中，有 $N$ 名参赛者。接下来，他们将享用寿司晚餐。 每位参赛者都有一项「空腹度」的整数值。这个值是独立随机分配的，具体如下： - 空腹度为 $x_1$ 的概率是 $\frac{p_1}{q}$； - 空腹度为 $x_2$ 的概率是 $\frac{p_2}{q}$； - 以此类推，空腹度为 $x_M$ 的概率是 $\frac{p_M}{q}$。 作为寿司厨师，你有 $N$ 个盘子，每个盘子至少需要放一个寿司。每个盘子可以放不同数量的寿司，不受限制。 这些盘子会被送到参赛者的餐桌上，参赛者们会各自取一个盘子。如果某一位空腹度为 $x$ 的参赛者取了一个有 $y$ 个寿司的盘子，他的「不满度」为 $|x - y|$。 参赛者们会选择盘子，以使得所有人的不满度总和最小。我们称这个总和为「不适应度」。 你的任务是安排寿司数量，使得不适应度的期望值最小。请计算这一情况下的不适应度的最小期望值。

输入以以下格式给出： > $N$ $M$ $q$ $x_1$ $p_1$ $x_2$ $p_2$ ... $x_M$ $p_M$

输出不适应度期望值的最小可能值。 如果与正确答案的绝对误差或相对误差在 $\pm\ 0.0001$ 以内，则视为正确。 ## 数据范围与说明 - $N$ 是 $1$ 到 $2,000$ 之间的整数。 - $M$ 是 $1$ 到 $2,000$ 之间的整数。 - $1 \leq x_1 < x_2 < \ldots < 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 + \ldots + p_M = q$。 ### 示例说明 **示例 1** 只有 $1$ 名参赛者，空腹度以 $30/100 = 0.3$ 的概率为 $1$，以 $20/100 = 0.2$ 的概率为 $3$，以 $50/100 = 0.5$ 的概率为 $9$。设想在一个盘子中放 $6$ 个寿司，唯一的参赛者取这个盘子，那么不适应度的期望值为 $|1-6| \times 0.3 + |3-6| \times 0.2 + |9-6| \times 0.5 = 3.6$，这是最优解。 **示例 2** 有 $2$ 名参赛者，称作 A 和 B。他们的空腹度分布和示例 1 中的相同。有两个盘子，盘子 1 和盘子 2。假设盘子 1 中有 $9$ 个寿司，盘子 2 中有 $1$ 个。 例如，当 A 和 B 的空腹度分别以概率 $30/100 \times 20/100$ 为 $1$ 和 $3$ 时，A 取盘子 2，B 取盘子 1时，总不满度为 $|1-1| + |3-9| = 6$。仔细计算其他情况后总结得出放置寿司如此时，不适应度期望值为 $4.16$。 **示例 3** 将 $111,111$ 个寿司放在第一个盘子，$999,999$ 放在第二个盘子，$555,555$ 放在第三个盘子时，不适应度的期望值为 $666,666$，这是最优解。 **本翻译由 AI 自动生成**

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