你本质上是一名环保活动家,但现实很残酷,你只是电影院的收银员。但你仍然可以做点什么!
您有 $$$n$$$ 门票可供出售。第 $$$i$$$ 票的价格为 $$$p_i$$$。作为出纳员,您可以选择门票的出售顺序(即门票的排列)。您知道电影院参与了两个生态恢复计划,并将其按照您选择的顺序应用:
- 按您选择的顺序,第 $$$a$$$ 售出的每张门票(第 $$$a$$$、第 $$$2a$$$、第 $$$3a$$$ 等)的价格 $$$x\%$$$ 旨在用于可再生能源的研究和传播。
- 按您选择的顺序,第 $$$b$$$ 售出的每张门票(第 $$$b$$$、第 $$$2b$$$、第 $$$3b$$$ 等)的价格 $$$y\%$$$ 旨在减少污染。
如果门票同时包含在两个计划中,则 $$$(x + y) \%$$$ 用于环保活动。此外,众所周知,所有价格都是 $$$100$$$ 的倍数,因此无需进行任何舍入。
例如,如果您想以 $$$[400, 100, 300, 200]$$$ 的价格出售门票,并且电影院为每张 $$$2$$$ 售出的门票支付 $$$10\%$$$,并为每张 $$$3$$$ 售出的门票支付 $$$20\%$$$,然后按顺序排列它们$$$[100, 200, 300, 400]$$$ 将导致贡献等于 $$$100 \cdot 0 + 200 \cdot 0.1 + 300 \cdot 0.2 + 400 \cdot 0.1 = 120$$$。但按 $$$[100, 300, 400, 200]$$$ 的顺序排列它们将导致 $$$100 \cdot 0 + 300 \cdot 0.1 + 400 \cdot 0.2 + 200 \cdot 0.1 = 130$$$。
自然等不及了,所以你决定以这样的方式改变门票的顺序,让节目的总贡献在最低售票数中至少达到$$$k$$$。或者说这是不可能的。换句话说,找到需要出售的最少门票数量才能赚取至少 $$$k$$$。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 独立查询的数量。每个查询由 $$$5$$$ 行组成。
每个查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 门票数量。
第二行包含$$$n$$$整数$$$p_1, p_2, \dots, p_n$$$ ($$$100 \le p_i \le 10^9$$$, $$$p_i \bmod 100 = 0$$$)——对应的门票价格。
第三行包含两个整数 $$$x$$$ 和 $$$a$$$ ($$$1 \le x \le 100$$$, $$$x + y \le 100$$$, $$$1 \le a \le n$$$) — 第一个程序的参数。
第四行包含两个整数 $$$y$$$ 和 $$$b$$$ ($$$1 \le y \le 100$$$, $$$x + y \le 100$$$, $$$1 \le b \le n$$$)——第二个程序的参数。
第五行包含单个整数 $$$k$$$ ($$$1 \le k \le 10^{14}$$$) — 所需的总贡献。
保证每次测试的门票总数不超过$$$2 \cdot 10^5$$$。
输出
打印 $$$q$$$ 整数 - 每个查询一个。
对于每个查询,如果您可以按任何顺序出售门票,请打印您需要出售的最小门票数量,以使总生态贡献至少为 $$$k$$$。
如果出售所有门票无法达到总贡献,请打印$$$-1$$$。
示例
输入 #1
4 1 100 50 1 49 1 100 8 100 200 100 200 100 200 100 100 10 2 15 3 107 3 1000000000 1000000000 1000000000 50 1 50 1 3000000000 5 200 100 100 100 100 69 5 31 2 90
输出 #1
-1 6 3 4
注意
在第一个查询中,总贡献等于 $$$50 + 49 = 99 < 100$$$,因此不可能收集到足够的钱。
在第二个查询中,您可以按以下方式重新排列门票:$$$[100, 100, 200, 200, 100, 200, 100, 100]$$$,第一个 $$$6$$$ 门票的总贡献等于 $$$100 \cdot 0 + 100 \cdot 0.1 + 200 \cdot 0.15 + 200 \cdot 0.1 + 100 \cdot 0 + 200 \cdot 0.25 = 10 + 30 + 20 + 50 = 110$$$。
在第三个查询中,每张门票的全价都用于环保活动。
在第四个查询中,您可以将门票重新排列为 $$$[100, 200, 100, 100, 100]$$$,前 $$$4$$$ 门票的总贡献为 $$$100 \cdot 0 + 200 \cdot 0.31 + 100 \cdot 0 + 100 \cdot 0.31 = 62 + 31 = 93$$$。