Problema número 557

Haciendo largos

Tiempo máximo: 2,000 sMemoria máxima: 4096 KiB
Nadador en una piscina olímpica, visto desde debajo del agua

El médico me ha recomendado nadar para cuidar mi espalda, así que desde esta semana estoy yendo a la piscina. Al ser mis primeros días estoy haciendo series cortas, de sólo dos largos, y descanso un rato entre series. Pero como estoy en muy baja forma, necesito hacer los descansos cada vez más largos. Así, en mi primer día de natación mi primer descanso fue de un minuto, el segundo de un minuto y medio, el tercero de dos minutos y así sucesivamente. Cada descanso duró 30 segundos más que el anterior y, como todos los largos los hice en el mismo tiempo (30 segundos), tardé 37 minutos en nadar 20 largos.

Así las cosas, me pregunto de manera general cuánto tardaría en hacer un determinado número de largos en función del tiempo por largo, el número de largos por serie y los tiempos de descanso entre series.

Entrada

La primera línea de la entrada contiene un número que indica cuántos casos de prueba habrá que procesar.

Cada caso de prueba consiste en una línea con 5 números enteros: N, T, M, DI. El primer entero, N, es el número de largos que quiero nadar. El segundo número, T, es el tiempo en segundos que tardo en hacer un largo. El tercer entero, M, es el número de largos que hago en cada serie. Finalmente D indica el tiempo en segundos del primer descanso entre series, e I es la cantidad extra de descanso, en segundos, que necesito con cada serie adicional. Nótese que la última serie no tiene por qué estar completa.

Se satisfacen los siguientes límites: 1 ≤ N ≤ 100.000.000, 20 ≤ T ≤ 40, 1 ≤ M ≤ N y 0 ≤ DI ≤ 60.

Salida

Para cada caso de prueba, se escribirá una línea con el tiempo en segundos necesario para hacer los largos.

Entrada de ejemplo

2
20 30 2 60 30
20 30 2 60 60

Salida de ejemplo

2220
3300