幸运盒

题目描述

小明有 $n$ 个幸运盒，每次运转一个盒子的结果要么出现糖果，要么出现芥末。每一轮，小明可以每次选择恰好 $k$ 个盒子一起运转，每个盒子有 $p \%$ 的概率开出糖果，$\left (100-p \right) \%$ 的概率开出芥末；或者他可以选择这一轮使用法术：选择恰好 $t$ 个盒子，对这些盒子的开出糖果的概率进行调整，使这些盒子分别有 $p \%$，$\left( \min \left( p+1, 100 \right) \right) \%$，……，$\left( \min \left( p+t-1 , 100 \right) \right) \%$ 的概率获得糖果；当然，他也可以什么都不做，放弃这一轮。

简单来说，就是

一开始有$n$个盒子，最开始的时候盒子都是空的。

可以进行$m$次操作，每次操作有三种选择：

1. 什么也不做，此时盒子的状态维持不变
2. 选择$k$个盒子，清空里面的东西，每个盒子现在有 $p \%$ 的概率开出糖果，然后重新开启它们
3. 选择$t$个盒子，清空里面的东西，每个盒子现在有 $p \%$，$\left( \min \left( p+1, 100 \right) \right) \%$，……，$\left( \min \left( p+t-1 , 100 \right) \right) \%$ 的概率获得糖果，然后重新开启它们

小明很聪明，每一轮都会选择最优的策略运转这些盒子，包括选择 $k$ 个盒子重新运转，或者选择 $t$ 个盒子使用法术，亦或是放弃这一轮的运转。他可以进行 $m$ 轮操作，在所有操作结束之前他不能拿走盒子里的东西。他想知道 $m$ 轮操作之后，他期望获得多少的糖果。

输入

第一行一个整数 $T$，表示数据组数。

对每组数据，输入一行五个整数：$n$，$m$，$t$，$k$，$p$，分别表示盒子的数量 $n$、运转轮数 $m$、使用法术需要选择的盒子数量 $t$、不使用法术需要选择的盒子数量 $k$，以及 $p$ 表示初始概率 $p \%$。

$ 1 \le T \le 100, 1 \le n \le 500, 1 \le m \le 500, 1 \le t \le 20, t \le k \le n, 1 \le p \le 100, $

对于 $T$ 组数据中 $90 \%$ 组的数据，$1 \le n \le 50$， $1 \le m \le 50$，$1 \le t \le 10$。

输出

每组测试数据输出一行，一个 $5$ 位小数，表示最佳策略下的期望。

输入样例

2
500 500 19 300 50
39 42 4 27 86

输出样例

497.89734
39.00000