题目描述

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

小明在逛超市。

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

超市有下面的打折政策：

• 每名顾客有 $a$ 张折扣券，可以让一件商品的价格打折（如果此商品原价为 $p_i$，那么使用此优惠券后，价格变为 $p_i \cdot x\%$
• 每名顾客有 $b$ 张立减券，可以让一件商品的价格减小 $y$（如果此商品原价小于 $y$，那么可以花费 $0$ 买下）。
• 每个商品最多使用 $1$ 张优惠券。

请求出小明可能付出的最小的花费。

输入格式

第一行包含一个整数 $T(1 \le T \le 10^5)$，表示测试用例的组数。

对于每组测试用例：

第一行包含 $5$ 个整数 $n(1 \le n \le 2 \times 10^5), a(1 \le a \le n), b(1 \le b \le n), x(1 \le x \le 99), y(1 \le y \le 10^4)$

第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n(1 \le p_i \le 10^4)$，表示商品的价格

保证对于所有的测试用例，$n$ 的总和不超过 $2 \cdot 10^5$

输出格式

对于每组测试用例： 仅输出一行，包含一个实数，表示答案。如果你的答案和标准答案的绝对误差或相对误差不超过 $10^{-4}$，则你的答案会被视为正确。

7
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
2 1 1 70 40
100 30

100.0000
72.5000
4.6800
600.0000
17.0000
1700.0000
70.0000

提示

【样例解释 1】

• 对商品 1 使用折扣券，那么商品 1 花费 $100 \cdot 50\% = 50$
• 对商品 2 使用折扣券，那么商品 2 花费 $100 \cdot 50\% = 50$
• 对商品 3 使用立减券，那么商品 3 花费 $100 - 50 = 50$
• 总花费 $50 + 50 + 0 = 100$

【样例解释 2】

• 对商品 1 使用折扣券，那么商品 1 花费 $100 \cdot 50\% = 50$
• 对商品 2 使用立减券，那么商品 2 花费 $100 - 200\% = -100$，不用花钱
• 对商品 3 使用折扣券，那么商品 3 花费 $45 \cdot 50\% = 22.5$
• 总花费 $50 + 0 + 22.5 = 72.5$

【样例解释 7】

• 对商品 1 使用折扣券，那么商品 1 花费 $100 \cdot 70\% = 70$
• 对商品 2 使用立减券，那么商品 2 花费 $30 - 40 = -10$，商品 2 不需要花钱
• 总花费 $70 + 0 = 70$
• 样例 7 告诉我们，下面的贪心策略是不对的
• 按价格从大到小考虑，当前商品如果使用折扣券更优惠（折扣券还有剩余），就用折扣券，否则用立减券
• 事实上，商品 1 使用折扣券，花费 $100 \cdot 70\% = 70$
• 商品 1 使用立减券，花费 $100 - 40 = 60$
• 商品 1 使用立减券更优化，但最后的结果是使用折扣券

数据规模与限制

• $1 \le n \le 2 \times 10^5$
• $1 \le a, b \le n$
• $1 \le x \le 99, 1 \le y \le 10^4$
• $1 \le p_i \le 10^4$
• 1s, 1024KiB for each test case.

来源