CF2178H Create or Duplicate

Santa realized that hand-drawing circles takes too long, so he has turned to magic to meet his production quotas. There are three types of presents with distinct values $ a $ , $ b $ , and $ c $ . Initially, Santa has exactly one present of each type. You are given two integers $ m $ and $ k $ , representing Santa's favorite number and the cost of duplication, respectively. Santa can cast the following two types of spells any number of times (possibly zero): 1. Create — Choose a type of present and create one additional present of that type. This spell costs $ x $ mana, where $ x\in \{a,b,c\} $ is the value of the chosen type. 2. Duplicate — Choose a type of present and duplicate all presents of that type. This spell costs $ k $ mana. Santa wants to perform a sequence of spells such that the sum of the values of all presents is a multiple of $ m $ after the spells. Determine the minimum amount of mana Santa needs to achieve this. It can be shown that, under the given constraints, such a sequence of spells always exists.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The only line of each test case contains five integers $ a $ , $ b $ , $ c $ , $ m $ , and $ k $ ( $ 1\leq a< b< c< m\leq 5\cdot 10^5 $ , $ 1\leq k\leq 5\cdot 10^5 $ ). It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 5\cdot 10^5 $ . It is guaranteed that the sum of $ k $ over all test cases does not exceed $ 5\cdot 10^5 $ .

For each test case, output a single integer — the minimum amount of mana Santa needs to make the sum of the values of all presents a multiple of $ m $ .

Let $ \ell $ be the list of values of presents and $ \operatorname{sum}(\ell) $ be the sum of all elements in $ \ell $ . In the first test case, below is an optimal sequence of operations: \#OperationValue $ \ell $ after operation $ \operatorname{sum}(\ell) $ Cost0—— $ [1, 2, 3] $ $ 6 $ —1Create $ 3 $ $ [1, 2, 3, 3] $ $ 9 $ $ 3 $ 2Create $ 3 $ $ [1, 2, 3, 3, 3] $ $ 12 $ $ 3 $ 3Duplicate $ 3 $ $ [1, 2, 3, 3, 3, 3, 3, 3] $ $ 21 $ $ 4 $ $ 21=7\cdot 3 $ Total: $ 10 $ In the second test case, it is optimal to not perform any operations because $ 3+4+5=12 $ is already a multiple of $ 12 $ . In the third test case, below is an optimal sequence of operations: \#OperationValue $ \ell $ after operation $ \operatorname{sum}(\ell) $ Cost0—— $ [3, 12, 14] $ $ 29 $ —1Duplicate $ 12 $ $ [3, 12, 12, 14] $ $ 41 $ $ 1 $ 2Duplicate $ 14 $ $ [3, 12, 12, 14, 14] $ $ 55 $ $ 1 $ 3Create $ 14 $ $ [3, 12, 12, 14, 14, 14] $ $ 69 $ $ 14 $ 4Duplicate $ 3 $ $ [3, 3, 12, 12, 14, 14, 14] $ $ 72 $ $ 1 $ $ 72=18\cdot 4 $ Total: $ 17 $