Descrizione

Sei il capitano della squadra scolastica di programmazione competitiva e stai guidando i tuoi compagni di classe a Chongqing per partecipare al CCPC. Secondo la tradizione della squadra, in qualità di capitano, devi offrire un pasto ai tuoi compagni e hai intenzione di mangiare la specialità locale: l'hot pot.

Secondo le statistiche, nella squadra ci sono $x$ studenti che accettano solo cibo piccante, $y$ studenti che accettano solo cibo non piccante e $z$ studenti che accettano sia cibo piccante che non piccante. Il ristorante di hot pot che visitate offre tre tipi di pentole:

• Pentola piccante, che può servire al massimo due studenti che accettano cibo piccante, al costo di $a$ yuan a porzione.
• Pentola mista, che può servire al massimo uno studente che accetta cibo piccante e al massimo uno studente che accetta cibo non piccante, al costo di $b$ yuan a porzione.
• Pentola non piccante, che può servire al massimo due studenti che accettano cibo non piccante, al costo di $c$ yuan a porzione.

Vuoi sapere la quantità minima di denaro necessaria per garantire che tutti gli studenti possano mangiare l'hot pot secondo le proprie preferenze.

Input

Ci sono più casi di test in un singolo file di input. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 2025$), che indica il numero di casi di test.

Per ciascun caso di test:

• Ogni riga contiene $6$ interi positivi $x, y, z, a, b, c$ ($1 \le x, y, z, a, b, c \le 2025$), che rappresentano il numero di studenti in ciascuna categoria e i prezzi dei tre tipi di hot pot.

Output

Per ciascun caso di test, stampa un singolo intero su una singola riga, che rappresenta il costo minimo possibile per garantire che tutti gli studenti possano mangiare l'hot pot secondo le proprie preferenze.

Esempio

Input di esempio 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

Output di esempio 1

8
3
9
39
29
26

Nota

• Nel primo esempio, puoi far mangiare cibo piccante a tutti gli studenti con preferenza mista, quindi ordinare tre pentole piccanti e una pentola mista, con un costo totale di $1 \times 3 + 5 \times 1 = 8$.
• Nel secondo esempio, puoi far sì che tra gli studenti con preferenza mista due mangino piccante e due mangino non piccante, quindi ordinare tre pentole miste, con un costo totale di $1 \times 3 = 3$.