H. Создать или дублировать
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Санта понял, что рисовать круги вручную занимает слишком много времени, поэтому он обратился к магии, чтобы выполнить свои производственные квоты.

Существует три типа подарков с различными значениями $$$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$$$ будет списком значений подарков, а $$$\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$$$