Migrated from Lutece 2782 卷不动了就来打牌吧

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

刚算完卖瓜钱的 MichaelZona 和 laduiw 心情都很好，准备玩一下卡牌游戏寻找童年的记忆。于是他俩向路过的 zhimahuhu 要了一套卡牌。

这套卡牌共有 $n$ 张。游戏时，将其一字排开，并且编号为 $1$ ~ $n$。每张卡牌都有一个技能。并且第 $i$ 张卡牌的技能发动概率为 $p_i$，如果技能成功发动，则会对对方造成 $d_i$ 点伤害。这是唯一能让对方收到伤害的途径。即 $0 \lt p_i \lt 1$。 一局游戏一共有 $r$ 轮。每一轮都将从第一张卡牌开始，按照顺序依次考虑到每张卡牌。在一轮中，对于依次考虑的每一张卡牌会进行如下操作：

1. 如果这张卡牌在这一局游戏中已经发动过技能，则:
   1. 如果这张卡牌不是最后一张，则跳过该牌（考虑下一张卡牌）;
   2. 否则（是最后一张），结束这一轮游戏。
2. 若 $1$ 不成立，即这张卡牌在这一局游戏中没有发动过技能，假设这张卡牌为第 $i$ 张
   1. 将其以 $p_i$ 的概率发动技能。
   2. 如果技能发动，则对对方造成 $d_i$ 点伤害，并结束这一轮。
   3. 如果这张卡牌已经是最后一张（即 $i$ 等于 $n$ ），则结束这一轮；否则，考虑下一张卡牌。

由于 MichaelZona 连一手顺子加枪的斗地主都能打输，卡牌游戏对他来说就是一项看脸的游戏。但是 MichaelZona 属于经典的又菜又爱玩，他想让聪明的你帮他算一下能对 laduiw 造成伤害的期望值是多少。

Input

输入的第一行包含一个整数 $T$，代表测试数据组数。

接下来一共 $T$ 组数据。

每组数据的第一行包含两个用空格分开的整数 $n$ 和 $r$，分别代表卡牌的张数和游戏的轮数。

接下来 $n$ 行，每行包含一个实数和一个整数，由空格隔开，描述一张卡牌。第 $i$ 行的两个数为 $p_i$ 和 $d_i$ ，分别代表第 $i$ 张卡牌技能发动的概率和技能发动造成的伤害。保证 $p_i$ 最多包含 $4$ 位小数，且为一个合法的概率。

Output

对于每组数据，输出一行，包含一个实数，为这套卡牌在这一局游戏中造成的伤害的期望值。

对于每一行输出，结果保留五位小数。

Samples

1
3 2
0.5000 2
0.3000 3
0.9000 1

3.26602

Constraints

对于所有测试数据， $1 \leq T \leq 444$ ， $1 \leq n \leq 220$ ， $0 \leq r \leq 132$ ， $0 \lt pi \lt 1$ ，$0 \leq di \leq 1000$

Resources

2022 UESTC ICPC Training for Dynamic Programming