CFCF2178H.Create or Duplicate

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

圣诞老人发现手绘圆圈太耗时，因此他决定借助魔法来实现生产目标。

有三种不同价值的礼物，其价值分别为 $a$ 、 $b$ 和 $c$ 。初始时，圣诞老人各有一种类型的礼物各一件。

你将得到两个整数 $m$ 和 $k$ ，分别代表圣诞老人最喜欢的数字以及复制魔法的花费。圣诞老人可以不限次数地施放以下两种魔法（可能为零次）：

创造——选择一种礼物类型，额外创造一个同类型礼物。此法术消耗 $x$ 点魔力，其中 $x\in \{a, b, c\}$ ，表示所选类型的价值。
复制——选择一种礼物类型，并将所有该类型的礼物复制一份。此法术消耗 $k$ 点魔力。

圣诞老人希望通过一系列法术操作，使所有礼物的总价值之和成为 $m$ 的倍数。

请你计算，为达成要求，圣诞老人至少需要消耗多少魔力。在给定约束下，总有一种可行方案。

输入格式

每个测试点包含多组用例。第一行为测试用例个数 $t$ （ $1 \leq t \leq 10^4$ ）。接下来每个测试用例一行，包含五个整数 $a$ 、 $b$ 、 $c$ 、 $m$ 、 $k$ （ $1 \leq a < b < c < 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$ 的倍数所需的最小魔力值。

输入输出样例

输入#1

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

输出#1

说明/提示

令 $\ell$ 表示当前所有礼物的价值序列， $\operatorname{sum}(\ell)$ 为其元素之和。

样例第一个用例的最优操作如下：

#	操作	操作类型	操作后 $\ell$	$\operatorname{sum}(\ell)$	花费
0	—	—	$[1, 2, 3]$	$6$	—
1	Create $3$	创造 $3$	$[1, 2, 3, 3]$	$9$	$3$
2	Create $3$	创造 $3$	$[1, 2, 3, 3, 3]$	$12$	$3$
3	Duplicate $3$	复制 $3$	$[1, 2, 3, 3, 3, 3, 3, 3]$	$21$	$4$
				$21 = 7 \times 3$
				总计	$10$

样例第二个用例，不操作即最优，因为 $3+4+5=12$ 已经是 $12$ 的倍数。

样例第三个用例的最优操作如下：

#	操作	操作类型	操作后 $\ell$	$\operatorname{sum}(\ell)$	花费
0	—	—	$[3, 12, 14]$	$29$	—
1	Duplicate $12$	复制 $12$	$[3, 12, 12, 14]$	$41$	$1$
2	Duplicate $14$	复制 $14$	$[3, 12, 12, 14, 14]$	$55$	$1$
3	Create $14$	创造 $14$	$[3, 12, 12, 14, 14, 14]$	$69$	$14$
4	Duplicate $3$	复制 $3$	$[3, 3, 12, 12, 14, 14, 14]$	$72$	$1$
				$72 = 18 \times 4$
				总计	$17$

首页