Условие

Вы — капитан школьной команды по спортивному программированию и привезли своих одноклассников в Чунцин для участия в соревновании CCPC. По традиции команды, как капитан, вы должны угостить одноклассников обедом, и вы планируете поесть местное фирменное блюдо — хого (китайский самовар).

Согласно статистике, в команде есть $x$ учеников, которые едят только острую пищу, $y$ учеников, которые едят только неострую пищу, и $z$ учеников, которые едят как острую, так и неострую пищу. Ресторан хого, в который вы пришли, предлагает три вида котлов:

• Острый котёл, рассчитанный максимум на двух учеников, которые едят острую пищу, стоимостью $a$ юаней за порцию.
• Смешанный котёл (юаньян), рассчитанный максимум на одного ученика, который ест острую пищу, и максимум на одного ученика, который ест неострую пищу, стоимостью $b$ юаней за порцию.
• Неострый котёл, рассчитанный максимум на двух учеников, которые едят неострую пищу, стоимостью $c$ юаней за порцию.

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

Входные данные

В одном входном файле содержится несколько наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T \le 2025$) — количество наборов входных данных.

Для каждого набора входных данных:

• Каждая строка содержит $6$ положительных целых чисел $x, y, z, a, b, c$ ($1 \le x, y, z, a, b, c \le 2025$) — количество учеников каждой категории и цены трёх видов котлов хого.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — минимально возможную стоимость, позволяющую накормить всех учеников хого в соответствии с их предпочтениями.

Пример

Входные данные 1

6
3 1 4 1 5 9
1 1 4 5 1 4
1 5 2 8 2 3
9 6 2 3 5 10
1 5 8 2 8 7
1 9 5 10 3 5

Выходные данные 1

8
3
9
39
29
26

Примечание

• В первом примере можно предложить всем ученикам со смешанными предпочтениями есть острую пищу, а затем заказать три острых котла и один смешанный котёл, общая стоимость составит $1 \times 3 + 5 \times 1 = 8$.
• Во втором примере можно предложить двум ученикам со смешанными предпочтениями есть острую пищу, а двум другим — неострую, и заказать три смешанных котла, общая стоимость составит $1 \times 3 = 3$.