Kevin逛超市 2 (困难版本)

题号：NC264531
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\sf Take\ that\ money,\ and\ watch\ it\ burn$

$\sf Sink\ in\ the\ river,\ the\ lessons\ I’ve\ learned$

—— $Counting\ Stars,\ \text{OneRepublic}$

两个版本唯一的不同是：简单版本中折扣券和立减券的数量均为 $1$ ，困难版本中折扣券和立减券的数量为给定值。

氧气少年在逛超市。

他总共买了 $n$ 件商品，第 $i$ 种商品的价格为 $p_i$ 。

超市有下面的打折政策：

请求出氧气少年可能付出的最小的花费。

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

第一行包含五个整数 。
第二行包含  个整数 ，表示商品的价格。

保证对于所有的测试用例， 的总和不超过 。

对于每组测试用例：

仅输出一行，包含一个实数，表示答案。如果你的答案和标准答案的绝对误差或相对误差不超过 ，则你的答案会被视为正确。

示例1

复制

6
3 2 1 50 50
100 100 50
3 3 1 50 200
100 100 45
3 2 2 36 3
5 8 1
3 3 3 99 500
100 600 1000
3 3 3 1 1
100 600 1000
3 0 0 1 1
100 600 1000

复制

100.000000000000
72.500000000000
4.680000000000
600.000000000000
17.000000000000
1700.000000000000

对于第一组样例数据：
可以对编号为  的商品使用折扣券，对编号为  的商品使用立减券。

对于第二组样例数据：
可以对编号为  的商品使用折扣券，对编号为  的商品使用立减券。