← 返回题目列表

Codeforces · 2178/H

H. 创建或复制

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

圣诞老人意识到手绘圆圈需要太长时间,因此他转向魔法来满足他的生产指标。

礼物分为三种类型,具有不同的价值 $$$a$$$、$$$b$$$ 和 $$$c$$$。最初,圣诞老人有 正好一个 剩余怪兽的 每种类型的礼物。

给你两个整数 $$$m$$$ 和 $$$k$$$,分别代表圣诞老人最喜欢的数字和复制成本。圣诞老人可以施放以下两种咒语任意次数(可能为零):

  1. 创建 — 选择一种礼物类型并再创建一份该类型的礼物。此法术消耗 $$$x$$$ 法力,其中 $$$x\in \{a,b,c\}$$$ 是所选类型的值。
  2. 复制 — 选择一种礼物类型并复制该类型的所有礼物。该法术消耗$$$k$$$ 法力。

圣诞老人想要执行一系列咒语,使得所有礼物的值之和是咒语后 $$$m$$$ 的倍数。

确定圣诞老人实现这一目标所需的最低法力量。可以证明,在给定的约束下,这样的咒语序列总是存在的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含五个整数 $$$a$$$、$$$b$$$、$$$c$$$、$$$m$$$ 和 $$$k$$$ ($$$1\leq a \lt b \lt c \lt m\leq 5\cdot 10^5$$$、$$$1\leq k\leq 5\cdot 10^5$$$)。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$5\cdot 10^5$$$。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$5\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 圣诞老人需要使所有呈现值的总和达到 $$$m$$$ 倍数的最小法力值。

示例

输入
复制

7
1 2 3 21 4
3 4 5 12 34
3 12 14 18 1
6 7 8 10 3
100 103 282 488 221
307 2000 5096 12018 5764
194093 292793 395323 475619 490151

输出
复制

10
0
17
9
1227
35116
7050242

注意

令$$$\ell$$$ 为presents 的值列表,$$$\operatorname{sum}(\ell)$$$ 为$$$\ell$$$ 中所有元素的总和。

在第一个测试用例中,以下是最佳操作顺序:

#操作值操作后$$$\ell$$$$$$\operatorname{sum}(\ell)$$$成本
0——$$$[1, 2, 3]$$$$$$6$$$—
1创建$$$3$$$$$$[1, 2, 3, 3]$$$$$$9$$$$$$3$$$
2创建$$$3$$$$$$[1, 2, 3, 3, 3]$$$$$$12$$$$$$3$$$
3重复$$$3$$$$$$[1, 2, 3, 3, 3, 3, 3, 3]$$$$$$21$$$$$$4$$$
$$$21=7\cdot 3$$$总计:$$$10$$$

在第二个测试用例中,最好不执行任何操作,因为 $$$3+4+5=12$$$ 已经是 $$$12$$$ 的倍数。

在第三个测试用例中,以下是最佳操作顺序:

#操作值操作后$$$\ell$$$$$$\operatorname{sum}(\ell)$$$成本
0——$$$[3, 12, 14]$$$$$$29$$$—
1重复$$$12$$$$$$[3, 12, 12, 14]$$$$$$41$$$$$$1$$$
2重复$$$14$$$$$$[3, 12, 12, 14, 14]$$$$$$55$$$$$$1$$$
3创建$$$14$$$$$$[3, 12, 12, 14, 14, 14]$$$$$$69$$$$$$14$$$
4重复$$$3$$$$$$[3, 3, 12, 12, 14, 14, 14]$$$$$$72$$$$$$1$$$
$$$72=18\cdot 4$$$总计:$$$17$$$