Problem G
Great Expectations

A speedrun is a playthrough of a game with the intention to complete it as quickly as possible. When speedrunning, you usually follow a pre-planned path through the game. Along this path, there may be some places where you have to pull off a difficult technique, or trick, which may cause a delay if you fail to pull it off successfully. Luckily you can reset the game at any time: if you have made a few mistakes, you can start a new run, losing your progress but instantaneously starting over with a clean slate. You can do this as often as you like.

The game you are currently speedrunning has a record of $r$ seconds, which you intend to beat. You have discovered a path through the game that, in the best case, takes $n < r$ seconds. There are some tricks along the way, though: you know exactly where along the run they occur, what the probability is that you will pull them off successfully, and how many seconds you have to spend to recover if they fail.

Given this data, you want to find the optimal strategy for when to reset the game to minimise the expected time to set a new record. Write a program to determine what this smallest possible expected time is.

Input

The input consists of:

• One line with three integers $n$, $r$ and $m$ ($2 \leq n < r \leq 5\, 000$, $1 \le m \le 50$), where $n$ and $r$ are as described above and $m$ is the number of tricks.

• $m$ lines, each containing three numbers describing a trick:

  • An integer $t$ ($1 \le t < n$), the time in the route (assuming no failed tricks before) at which the trick occurs,

  • a real number $p$ ($0 < p < 1$ and $p$ has at most $6$ digits after the decimal point), the probability that the trick succeeds, and

  • an integer $d$ ($1 \le d \le 1\, 000$), the number of seconds required to recover in case the trick fails.

The tricks are given in sorted order by $t$, and no two tricks occur at the same time $t$ in the route.

You may assume that, without resetting, a single playthrough has a probability of at least $1$ in $50\, 000$ to succeed at improving the record.

Output

Output the expected time you will have to play the game to set a new record, assuming an optimal strategy is used. Your answer should have an absolute or relative error of at most $10^{-6}$.

Explanation of Sample Input 1

The record for this game is $111$ seconds, and your route takes $100$ seconds if everything goes right.

After playing for $20$ seconds, there is a trick with a $50\% $ success rate. If it succeeds, you keep playing. If it fails, you incur a $10$ second time loss: now the run will take at least $110$ seconds. It is still possible to set a record, but every other trick in the run has to be successful. It turns out to be faster on average to reset after failing the first trick.

Thus you repeat the first $20$ seconds of the game until the trick is successful: with probability $1/2$, it takes $1$ attempt; with probability $1/4$, it takes $2$ attempts; and so on. On average, you spend $40$ seconds on the first $20$ seconds of the route.

Once you have successfully performed the first trick, you want to finish the run no matter the result of the other tricks: it takes $80$ seconds, plus on average $1$ second loss from each of the remaining $4$ tricks. So the expected time until you set a record is $124$ seconds.

100 111 5
20 0.5 10
80 0.5 2
85 0.5 2
90 0.5 2
95 0.5 2

124

2 4 1
1 0.5 5

3

10 20 3
5 0.3 8
6 0.8 3
8 0.9 3

18.9029850746

10 50 1
5 0.5 30

15