速通（speedrun）是指以尽可能快地完成游戏为目的的游玩过程。在进行速通时，你通常会遵循一条预先规划好的游戏路径。在这条路径上，可能会有一些地方需要你完成高难度的技巧（trick），如果失败，可能会导致延误。幸运的是，你可以随时重置游戏：如果你犯了一些错误，可以开始新的一轮，虽然会失去当前的进度，但可以立即从头开始。你可以根据需要随时进行重置。

你目前正在速通的游戏纪录为 $r$ 秒，你打算打破这个纪录。你已经发现了一条游戏路径，在最佳情况下，该路径耗时 $n < r$ 秒。然而，沿途存在一些技巧：你确切地知道它们在路径中的位置、成功完成它们的概率，以及如果失败需要花费多少秒来恢复。

给定这些数据，你希望找到最优策略，确定何时重置游戏以最小化打破纪录的期望时间。编写一个程序来确定这个最小的期望时间。

输入格式

输入包含： 一行，包含三个整数 $n, r$ 和 $m$ ($2 \le n < r \le 5\,000, 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 1\,000$)，表示技巧失败时需要恢复的秒数。

技巧按 $t$ 的升序给出，且路径中不会有两个技巧在同一时间 $t$ 发生。 你可以假设，在不重置的情况下，单次游玩成功打破纪录的概率至少为 $1/50\,000$。

输出格式

输出在采用最优策略的情况下，打破纪录所需的期望时间。你的答案应具有不超过 $10^{-6}$ 的绝对或相对误差。

样例

输入 1

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

输出 1

124

说明 1

该游戏的纪录是 111 秒，如果一切顺利，你的路径耗时 100 秒。 在游玩 20 秒后，有一个成功率为 50% 的技巧。如果成功，你继续游玩。如果失败，你会损失 10 秒：此时该轮游戏至少需要 110 秒。虽然仍有可能打破纪录，但路径中剩下的每个技巧都必须成功。事实证明，在第一个技巧失败后重置平均而言更快。 因此，你重复游戏的前 20 秒直到技巧成功：以 $1/2$ 的概率，需要 1 次尝试；以 $1/4$ 的概率，需要 2 次尝试，以此类推。平均而言，你在路径的前 20 秒上花费了 40 秒。 一旦你成功完成了第一个技巧，无论其他技巧的结果如何，你都希望完成这一轮：这需要 80 秒，加上其余 4 个技巧平均每次 1 秒的损失。因此，直到你打破纪录的期望时间为 124 秒。

输入 2

2 4 1
1 0.5 5

输出 2

3

输入 3

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

输出 3

18.9029850746

输入 4

10 50 1
5 0.5 30

输出 4

15