← 返回题目列表

Codeforces · 1223/C

C. 拯救自然

中文机器翻译题面 查看原题

你本质上是一名环保活动家,但现实很残酷,你只是电影院的收银员。但你仍然可以做点什么!

您有 $$$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$$$。