背景

译自 Northwestern Europe Regional Contest (NWERC) 2020。

题目描述

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}$。

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

提示

【样例 $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}$。