Problem L
Witchwood
Maaba is playing the game Lumberjack, where the goal is to build log huts. Her current customer wants a hut made completely out of witchwood, which protects the hut from curses, hexes and magic spells – or at least that’s what the customer claims.
However, witchwood is not easy to handle: Some witch trees are highly volatile, and logs made from those trees will spontaneously combust when placed on the hut location. This will destroy both the original log and all logs nearby. Unfortunately, it is not possible to see the difference before the log is placed on the hut location, but it is known that a log from location $i$ will have probability $P_ i$ of combusting.
To avoid spending too much time, Maaba has devised a simple way to build the hut:
-
She uses $T_ i$ seconds to retrieve and place a single witchwood log from location $i$.
-
If the hut logs combust, she waits $K$ seconds to wait for the fire to stop, then collect the ashes. Afterwards, she starts over from scratch.
-
If nothing happens, she continues with the next log.
As all locations have an infinite supply of witch trees, Maaba knows she will be done eventually. However, she wonders how long it would take her on average, if she retrieves logs from the right location at the right time. Could you help her?
Input
The first line of the input consists of three integers
$N$, $M$, $K$: The number of logs required to
build the hut, the number of locations with witchwood, and the
time it takes for witchwood to stop burning.
Then follows $M$ lines,
each consisting of an integer $T_
i$, and a real number $P_
i$, representing the time it takes to retrieve a log
from $i$ and the
probability that the log will spontaneously combust when
placed.
Output
The output should be a single real number representing the expected time in seconds Maaba will use to build a log hut out of only witchwood. Your answer must have an absolute or relative error of at most $10^{-6}$.
Limits
-
$1 \leq N, M \leq 1000$
-
$0 \leq K \leq 1000$
-
$1 \leq T_ i \leq 1000$
-
$0 \leq P_ i < 1$
-
The result will always be less than $10^{30}$.
-
Real numbers in the input will have at most $20$ digits after the decimal point.
Sample Explanation
In the provided example, the optimal choice is to retrieve a log from $2$ when she has placed $0$ logs, a log from $0$ when she has placed $1$ log, and a log from $1$ when she has placed $2$ logs.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 1 8 0.5 20 0.3 1 0.8 |
79.0 |
