Beschreibung

Du bist der Kapitän des Schulteams für Programmierwettbewerbe und führst deine Mitschüler nach Chongqing, um am CCPC teilzunehmen. Gemäß der Tradition des Teams musst du als Kapitän deine Mitschüler zu einem Essen einladen, und du planst, die lokale Spezialität – Feuertopf (Hot Pot) – zu essen.

Laut Statistik gibt es im Team $x$ Schüler, die nur scharfes Essen akzeptieren, $y$ Schüler, die nur mildes (nicht scharfes) Essen akzeptieren, und $z$ Schüler, die sowohl scharfes als auch mildes Essen akzeptieren. Das Feuertopf-Restaurant, das ihr besucht, bietet drei Arten von Töpfen an:

• Scharfer Topf, der höchstens zwei Schüler versorgen kann, die scharfes Essen akzeptieren, und $a$ Yuan pro Portion kostet.
• Gemischter Topf, der höchstens einen Schüler, der scharfes Essen akzeptiert, und höchstens einen Schüler, der mildes Essen akzeptiert, versorgen kann und $b$ Yuan pro Portion kostet.
• Milder Topf, der höchstens zwei Schüler versorgen kann, die mildes Essen akzeptieren, und $c$ Yuan pro Portion kostet.

Du möchtest wissen, wie viel Geld mindestens benötigt wird, um sicherzustellen, dass alle Schüler entsprechend ihren Vorlieben Feuertopf essen können.

Eingabe

Es gibt mehrere Testfälle in einer einzigen Eingabedatei. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 2025$), die die Anzahl der Testfälle angibt.

Für jeden Testfall gilt:

• Jede Zeile enthält $6$ positive ganze Zahlen $x, y, z, a, b, c$ ($1 \le x, y, z, a, b, c \le 2025$), die die Anzahl der Schüler in jeder Kategorie sowie die Preise der drei Arten von Feuertöpfen darstellen.

Ausgabe

Gib für jeden Testfall eine einzelne ganze Zahl in einer eigenen Zeile aus, die die minimal möglichen Kosten darstellt, um sicherzustellen, dass alle Schüler entsprechend ihren Vorlieben Feuertopf essen können.

Beispiel

Beispieleingabe 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

Beispielausgabe 1

8
3
9
39
29
26

Hinweis

• Im ersten Beispiel kannst du alle Schüler mit gemischter Vorliebe scharf essen lassen und dann drei scharfe Töpfe und einen gemischten Topf bestellen, was Gesamtkosten von $1 \times 3 + 5 \times 1 = 8$ ergibt.
• Im zweiten Beispiel kannst du von den Schülern mit gemischter Vorliebe zwei scharf und zwei mild essen lassen und dann drei gemischte Töpfe bestellen, was Gesamtkosten von $1 \times 3 = 3$ ergibt.