Problem Description

The participants of the CODE FESTIVAL 2018 Finals are $ N $ people. They are about to have sushi for dinner.

Each participant has an integer value called hunger level. This value is determined independently for each participant as follows:

• With probability $\frac{p_1}{q}$, the hunger level is $ x_1 $, with probability $\frac{p_2}{q}$, the hunger level is $ x_2 $, ..., with probability $\frac{p_M}{q}$, the hunger level is $ x_M $.

You are a sushi chef. There are $ N $ plates in the kitchen, and you need to place at least one sushi on each plate. There is no limit on the number of sushi that can be placed on a plate, and different plates can have different numbers of sushi.

These $ N $ plates are then brought to the tables where the participants are seated, and each participant takes one plate.
When a participant with hunger level $ x $ takes a plate with $ y $ pieces of sushi, the dissatisfaction level of that participant is $ |x - y| $.
The participants know their own hunger levels, and they will take plates such that the total dissatisfaction level of all participants is minimized. The total dissatisfaction level at this time is called the incompatibility level.

You want to place the sushi on the plates such that the expected incompatibility level is minimized. Find the minimum achievable expected incompatibility level when sushi is placed on the plates in this manner.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the minimum achievable expected incompatibility level.
The answer will be considered correct if the absolute or relative error is within $\pm 0.0001$ from the judge's solution.

Sample Input and Output

Sample Input #1

1 3 100
1 30
3 20
9 50

Sample Output #1

3.6000000000

Sample Input #2

2 3 10
1 3
3 2
9 5

Sample Output #2

4.1600000000

Sample Input #3

3 2 2
111111 1
999999 1

Sample Output #3

666665.9999999997

Notes/Hints

Constraints

• $ N $ is an integer between $ 1 $ and $ 2000 $ inclusive.
• $ M $ is an integer between $ 1 $ and $ 2000 $ inclusive.
• $1 \leq x_1 < x_2 < x_3 < ... < x_M \leq 1000000$.
• $ p_i $ ( $1 \leq i \leq M$ ) is an integer between $ 1 $ and $ 1000000 $ inclusive.
• $ q $ is an integer between $ 1 $ and $ 1000000 $ inclusive.
• $ p_1 + p_2 + p_3 + ... + p_M = q $.

Sample Explanation 1

In this case, there is one participant whose hunger level is $ 1 $ with probability $ 30/100 = 0.3 $, $ 3 $ with probability $ 20/100 = 0.2 $, and $ 9 $ with probability $ 50/100 = 0.5 $. Consider placing $ 6 $ pieces of sushi on one plate. The expected incompatibility level, which is also the expected dissatisfaction level of the only participant, is $|1-6| \times 0.3 + |3-6| \times 0.2 + |9-6| \times 0.5 = 3.6$. This is the minimum achievable value.

Sample Explanation 2

In this case, there are two participants, let's call them A and B. Their hunger level probability distributions are the same as the participant in Sample Input 1. Also, let's call the two plates plate 1 and plate 2. Consider placing $ 9 $ pieces of sushi on plate 1 and $ 1 $ piece of sushi on plate 2. For example, with probability $30/100 \times 20/100$, the hunger levels of A and B are $ 1 $ and $ 3 $ respectively. In this case, A takes plate 2 and B takes plate 1, minimizing their total dissatisfaction level to $ |1-1| + |3-9| = 6 $, so the incompatibility level is $ 6 $. By calculating similarly for other cases, we find that the expected incompatibility level when sushi is placed this way is $ 4.16 $. This is the minimum achievable value.

Sample Explanation 3

Placing $ 111111 $ pieces of sushi on the first plate, $ 999999 $ pieces on the second plate, and $ 555555 $ pieces on the third plate results in an expected incompatibility level of $ 666666 $, which is the minimum achievable value.

见题面 Input 部分

见题面 Output 部分