You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

提交前的提示： 如果想使用 C++ 输出指定位数的小数，可以使用 stdio.h 库或者 iostream 以及 iomanip 库。例：将浮点数 $x$ 保留三位小数输出可以使用 printf("%.3f", x) 或者 std::cout << std::fixed << std::setprecision(3) << x。

题目描述

清华大学的自动售货机一共有 $n$ 种饮料出售，每种饮料有自己的售价，并在售货机上各有一个出售口。购买第 $i$ 种饮料时，可以在第 $i$ 个出售口支付 $a_i$ 的价格，售货机便会在下方的出货处放出对应的饮料。

又到了清凉的夏日，自动售货机为每种饮料各进货了 $1$ 瓶存储在其中，供同学购买。但是，自动售货机却出现了一些故障，它有可能会出货不属于这个出售口的饮料。

对于第 $i$ 个出售口，支付 $a_i$ 的价格购买后，如果饮料 $i$ 与饮料 $b_i$ 都有存货，有 $p_i$ 的概率出货饮料 $i$，有 $1-p_i$ 的概率出货饮料 $b_i$。如果其中一个有存货，另一个已经没有存货，则将出货有存货的那一种饮料。如果两种饮料都没有存货，售货机将不会出货任何饮料并发出警报。即便最后你没有获得任何饮料，也需要支付 $a_i$ 的价格。

长颈鹿下楼来到这台售货机前，希望能买到最近火爆全网的饮料 $x$，此时售货机中 $n$ 种饮料都存货有 $1$ 瓶。由于它知道售货机有问题，因此决定采取这样的策略来购买：

• 在 $n$ 个出售口中等概率选择一个出售口 $s$ 开始购买，支付这个出售口的价格 $a_s$ 并得到出货。
• 当得到想要的饮料 $x$ 时，停止购买流程，满意欢喜地离去。
• 当得到不想要的饮料 $y$ 时，继续在第 $y$ 个支付口购买，支付 $a_y$ 的价格并等待出货。
• 当售货机发出警报时，停止购买流程，灰心丧气地离去。

现在他希望你告诉他，他这一次购买流程期望支付的价钱数量是多少？

输入格式

从标准输入读入数据。

第一行两个正整数 $n,x$。

接下来 $n$ 行每行两个整数与一个浮点数，其中第 $i$ 行表示 $a_i,b_i,p_i$。

输出格式

输出到标准输出。

一行一个实数表示答案，表示长颈鹿按他的策略买水期望支付的价钱。

记答案为 $a$，而你的输出为 $b$，那么当且仅当 $|a-b|<10^{-6}$ 时我们认为你的输出是正确的。

2 2
8 2 0.90
7 1 0.40

13.500000000

样例 1 解释

售货机里饮料 $1$ 与饮料 $2$ 各有一瓶，且当两瓶都还有存货时，在第 $1$ 个出售口有 $0.1$ 的概率买到饮料 $2$，在第 $2$ 个出售口有 $0.6$ 的概率买到饮料 $1$。

• 长颈鹿有 $0.5$ 的概率初始选择第 $1$ 个出售口开始购买，并支付 $8$ 元。
  • 有 $0.1$ 的概率直接出货饮料 $2$，一共支付 $8$ 元，这种情况的概率是 $0.05$。
  • 有 $0.9$ 的概率出货饮料 $1$，则长颈鹿会再支付 $8$ 元重新从第 $1$ 个出售口购买饮料。由于饮料 $1$ 已售空，第二次购买时必定直接出货饮料 $2$，一共支付 $16$ 元，这种情况的概率是 $0.45$。
• 长颈鹿有 $0.5$ 的概率初始选择第 $2$ 个出售口开始购买，并支付 $7$ 元。
  • 有 $0.4$ 的概率直接出货饮料 $2$，一共支付 $7$ 元，这种情况的概率是 $0.2$。
  • 有 $0.6$ 的概率出货饮料 $1$，则长颈鹿会再支付 $8$ 元重新从第 $1$ 个出售口购买饮料。由于饮料 $1$ 已售空，第二次购买时必定直接出货饮料 $2$，一共支付 $15$ 元，这种情况的概率是 $0.3$。

于是期望支付的价钱为 $8\times 0.05+16\times 0.45+7\times 0.2+15\times 0.3=13.5$。

子任务

对于所有数据，保证 $n\le 2000,~ 1\le b_i,x\le n,~ b_i\ne i,~ 0\le a_i\le 100~ , 0\le p_i\le 1$，且 $p_i$ 不超过两位小数。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（50 分）：保证 $n\le 10$。
• 子任务 2（30 分）：保证 $p_i = 0$。
• 子任务 3（20 分）：无特殊限制。