No testdata at current.

题目描述

《阿卡伊》是一款风靡全球的音乐游戏。

在这款游戏中，衡量游戏实力的方法是使用“潜力值”。

本题中简化了潜力值的计算方法。

• 首先，完成每一张谱面都会有一个单曲潜力值，如果这张谱面完成了多次，那么单曲潜力值取最高的一次计算。
• 玩家潜力值的计算方式是，取单曲潜力值最高的 $m$ 张谱面的单曲潜力值的平均数。如果玩家没有游玩至少 $m$ 张谱面，则剩余部分用 $0$ 补全。

输入格式

本题有多组测试数据，第一行一个正整数 $T$ 表示测试数据组数。

对于每组测试数据：

• 第一行，两个正整数 $n,m$，分别表示玩家的游玩次数和潜力值计算参数。
• 接下来 $n$ 行，两个只包含小写字母的字符串 $s_i,t_i$ 和一个浮点数 $ptt_i$，表示一次游玩记录。$s_i$ 的长度不超过 $20$，$t_i$ 的长度为 $3$。第 $i$ 条和第 $j$ 条游玩记录游玩的是相同的谱面当且仅当 $s_i=s_j$ 且 $t_i=t_j$。$ptt_i$ 表示该次游玩的单曲潜力值。

输出格式

对于每组测试数据，输出一个浮点数 $ptt$ 代表计算的玩家潜力值。你的答案被判为正确当且仅当其与正确答案的绝对误差或相对误差不超过 $10^{-4}$。如果你不知道什么是绝对误差和相对误差，你可以理解为可直接输出答案，不需要做额外处理。

1
5 3
extradimensional etr 13.07
extradimensional etr 13.08
testify byd 14.00
heavensdoor ftr 11.75
ifi ftr 13.06

13.38

提示

样例解释

$5$ 次游玩后，游玩过的谱面列表如下：

玩家潜力值为单曲潜力值最高的 $3$ 张谱面的单曲潜力值的平均数，即 $\dfrac{14.00+13.08+13.06}{3}=13.38$。

数据范围

对于 $100\%$ 的数据，$1\le T\le 10$，$1 \le m \le n \le 5\times{10}^4$，$0 \le ptt_i \le {10}^5$，$ptt_i$ 小数点后最多有 $4$ 位小数。