Descripción

Eres el capitán del equipo escolar de programación competitiva y llevas a tus compañeros de clase a Chongqing para participar en el CCPC. Según la tradición del equipo, como capitán, debes invitar a tus compañeros a una comida, y planeas comer la especialidad local: olla caliente (hot pot).

Según las estadísticas, hay $x$ estudiantes en el equipo que solo aceptan comida picante, $y$ estudiantes que solo aceptan comida no picante, y $z$ estudiantes que aceptan tanto comida picante como no picante. El restaurante de olla caliente que visitan ofrece tres tipos de ollas:

• Olla picante, que puede servir como máximo a dos estudiantes que acepten comida picante, con un costo de $a$ yuanes por ración.
• Olla mixta, que puede servir como máximo a un estudiante que acepte comida picante y como máximo a un estudiante que acepte comida no picante, con un costo de $b$ yuanes por ración.
• Olla no picante, que puede servir como máximo a dos estudiantes que acepten comida no picante, con un costo de $c$ yuanes por ración.

Quieres saber la cantidad mínima de dinero necesaria para garantizar que todos los estudiantes puedan comer olla caliente de acuerdo con sus preferencias.

Entrada

Hay múltiples casos de prueba en un solo archivo de entrada. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T \le 2025$), que indica el número de casos de prueba.

Para cada caso de prueba:

• Cada línea contiene $6$ enteros positivos $x, y, z, a, b, c$ ($1 \le x, y, z, a, b, c \le 2025$), que representan el número de estudiantes en cada categoría y los precios de los tres tipos de ollas calientes.

Salida

Para cada caso de prueba, imprime un solo entero en una sola línea, representando el costo mínimo posible para garantizar que todos los estudiantes puedan comer olla caliente según sus preferencias.

Ejemplo

Entrada de ejemplo 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

Salida de ejemplo 1

8
3
9
39
29
26

Nota

• En el primer ejemplo, puedes hacer que todos los estudiantes con preferencia mixta coman picante, y luego pedir tres ollas picantes y una olla mixta, con un costo total de $1 \times 3 + 5 \times 1 = 8$.
• En el segundo ejemplo, puedes hacer que de los estudiantes con preferencia mixta dos coman picante y dos coman no picante, y luego pedir tres ollas mixtas, con un costo total de $1 \times 3 = 3$.