ODI - Prácticas

Recientemente, Roberto consiguió un trabajo en traduciendo documentos legales de español a inglés. La compañía que lo contrató, TraduceMe.com, le paga dependiendo de la cantidad de páginas del documento: para documentos pequeños de 1 a 5 páginas, le paga $PPEQ; para documentos de más de 5 páginas, le paga $PGDE.

Roberto se toma MPEQ minutos para traducir un documento de hasta 5 páginas y MGDE minutos para documentos de más de 5 páginas.

Como está corto de tiempo, Roberto sólo tiene T minutos para trabajar en esas traducciones.  Una vez que Roberto completa un documento, puede empezar inmediatamente en la traducción de otro documento.

Sabiendo todo esto, ¿Cuál es la máxima cantidad de dinero que Roberto puede obtener traduciendo documentos en T minutos?

Asume que la TraduceMe.com tiene billones de documentos por traducir, por lo tanto Roberto no tiene que preocuparse de no tener suficientes documentos.  Por otro lado, TraduceMe.com no paga por documentos parcialmente traducidos, es decir, solo aceptan documentos completamente traducidos.

Entrada

La primera línea contiene un número entero C (1 ≤ C ≤ 10), que representa la cantidad de casos de pruebas a procesar.

Cada una de las siguientes C líneas contiene 5 números enteros separados por un espacio: T, PPEQ, PGDE, MPEQ y MGDE:

• T (1 ≤ T ≤ 1,000,000) es la cantidad de minutos que Roberto dispone para trabajar.

• Ppeq y PGDE (1 ≤ PPEQ ≤ PGDE ≤ 1,000) son los pagos que Roberto recibe por traducir documentos pequeños y grandes respectivamente.

• Mpeq y MGDE (1 ≤ MPEQ ≤ MGDE ≤ 1,000,000) son los tiempos que le toma a Roberto traducir un documento pequeño y grande, respectivamente.

Salida

Por cada caso de prueba, imprime una línea con el monto máximo de dinero que Roberto puede ganar traduciendo documentos.  La i-ésima línea de salida debe corresponder con el i-ésimo caso de prueba de entrada.

Ejemplo

En el primer caso de prueba, Roberto puede traducir dos documentos pequeños y dos grandes, para una ganancia total de 2 * $3 + 2 * $5 = $16.  En el segundo caso de prueba, la solución óptima es que Roberto traduzca 1 documento pequeño y 1 documento grande.