圣诞老人意识到手绘圆圈需要太长时间,因此他转向魔法来满足他的生产指标。
礼物分为三种类型,具有不同的价值 $$$a$$$、$$$b$$$ 和 $$$c$$$。最初,圣诞老人有 正好一个 剩余怪兽的 每种类型的礼物。
给你两个整数 $$$m$$$ 和 $$$k$$$,分别代表圣诞老人最喜欢的数字和复制成本。圣诞老人可以施放以下两种咒语任意次数(可能为零):
- 创建 — 选择一种礼物类型并再创建一份该类型的礼物。此法术消耗 $$$x$$$ 法力,其中 $$$x\in \{a,b,c\}$$$ 是所选类型的值。
- 复制 — 选择一种礼物类型并复制该类型的所有礼物。该法术消耗$$$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$$$ 倍数的最小法力值。
示例
输入复制
71 2 3 21 43 4 5 12 343 12 14 18 16 7 8 10 3100 103 282 488 221307 2000 5096 12018 5764194093 292793 395323 475619 490151
输出复制
1001791227351167050242
注意
令$$$\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$$$ | ||||