P17032 [NWERC 2020] 远大前程 / Great Expectations

译自 [Northwestern Europe Regional Contest (NWERC) 2020](http://2020.nwerc.eu)。

**Speedrun**（速通）指的是以尽可能快地完成游戏为目标进行的一次游戏流程。进行速通时，你通常会沿着一条预先规划好的路线游玩。沿着这条路线，可能会有一些位置需要你完成某个困难的技术动作，或者说技巧；如果你没能成功完成它，就可能会产生延误。幸运的是，你可以在任意时刻重开游戏：如果你犯了一些错误，就可以开始一次新的流程，丢失当前进度，但会立刻以干净的初始状态重新开始。你可以任意多次这样做。 你当前正在速通的游戏纪录是 $r$ 秒，而你打算打破这个纪录。你发现了一条通过游戏的路线，在最理想情况下，这条路线需要 $n < r$ 秒。不过，路线中有一些技巧：你准确知道它们在流程中的哪个时刻发生，知道自己成功完成每个技巧的概率，也知道如果技巧失败，需要花多少秒来恢复。 给定这些数据，你想找出什么时候重开游戏的最优策略，使得创造新纪录所需时间的期望最小。请编写程序，求出这个最小可能期望时间。

输入包括： - 第一行包含三个整数 $n$、$r$ 和 $m$（$2 \le n < r \le 5000$，$1 \le m \le 50$），其中 $n$ 和 $r$ 的含义如上，$m$ 是技巧的数量。 - 接下来 $m$ 行，每行包含三个数，描述一个技巧： - 一个整数 $t$（$1 \le t < n$），表示在路线中的哪个时刻会遇到该技巧；这里假设在此之前没有任何技巧失败。 - 一个实数 $p$（$0 < p < 1$，且 $p$ 的小数点后至多有 $6$ 位），表示该技巧成功的概率。 - 一个整数 $d$（$1 \le d \le 1000$），表示如果该技巧失败，需要花费多少秒来恢复。 技巧按 $t$ 的递增顺序给出，并且没有两个技巧在路线中的同一时刻 $t$ 发生。 你可以假设：如果不重开游戏，那么单次游玩成功刷新纪录的概率至少为 $50000$ 分之 $1$。

在使用最优策略的前提下，输出你为了创造新纪录需要游玩游戏的期望时间。你的答案的绝对误差或相对误差不应超过 $10^{-6}$。

【样例 $1$ 解释】 这款游戏的纪录是 $111$ 秒，而如果一切顺利，你的路线需要 $100$ 秒。 游玩 $20$ 秒后，有一个成功率为 $50\%$ 的技巧。如果它成功，你会继续游玩。如果它失败，你会损失 $10$ 秒：此时这次流程至少需要 $110$ 秒。仍然有可能创造纪录，但本次流程中之后的每个技巧都必须成功。事实证明，第一次技巧失败后重开，在平均意义上会更快。 因此，你会反复游玩游戏的前 $20$ 秒，直到这个技巧成功：以概率 $1/2$，它需要 $1$ 次尝试；以概率 $1/4$，它需要 $2$ 次尝试；依此类推。平均而言，你会在这条路线的前 $20$ 秒上花费 $40$ 秒。 一旦你成功完成了第一个技巧，你就会无论之后技巧的结果如何都完成这次流程：这需要 $80$ 秒，再加上剩余 $4$ 个技巧平均各造成 $1$ 秒损失。因此，直到你创造纪录为止的期望时间是 $124$ 秒。 【数据规模与约定】 - $2 \le n < r \le 5000$。 - $1 \le m \le 50$。 - 每个技巧满足 $1 \le t < n$，$0 < p < 1$，且 $p$ 小数点后至多 $6$ 位，$1 \le d \le 1000$。 - 技巧按 $t$ 递增顺序给出，且没有两个技巧在路线中的同一时刻 $t$ 发生。 - 不重开时，单次游玩成功刷新纪录的概率至少为 $1/50000$。 - 答案允许绝对或相对误差不超过 $10^{-6}$。