(Examen clasificatorio de la Olimpiada de Informática CDMX-EDOMEX ciclo 21-22 Nivel 02 Día 1 Problema 3)

Descripción

Juanito está trabajando en una fábrica de galletas, sus jefes le asignaron una tarea a Juanito de guardar galletas en ~N~ cajas, al inicio cada caja tenía una cantidad de ~G_i~ galletas, Juanito debe de acomodar ~K~ galletas y lo hace de la siguiente manera, escoge una caja ~i~ y agregas galletas a esa caja y repite este proceso, cuantas veces lo desee o se acaben las ~K~ galletas, cada caja debe de tener a lo más ~A~ galletas, si la caja tiene ~A~ galletas entonces Juanito ya no puede agregarle otra galleta.

Sus jefes tienen una manera peculiar de pagarle a Juanito la cual es mediante dos pagos: Por cada caja que tenga el máximo número de galletas ósea ~A~ galletas le pagaran ~M~ pesos. Por cada galleta en la caja con la menor cantidad de galletas (si hay más de ~1~ caja con la menor cantidad de galletas solo le pagan ~1~ caja) le pagaran ~B~ pesos.

Ayuda a Juanito a encontrar la manera óptima de repartir las ~K~ galletas en las ~N~ cajas para que pueda recibir el mayor pago posible.

Problema

Dado la cantidad de galletas que hay en cada caja ~G_i~ y la cantidad de galletas para acomodar, el máximo de galletas por caja, y las dos cantidades que le pagan, regresa la mayor cantidad de dinero que le pueden pagar a Juanito en su trabajo.

Entrada

En la primera línea ~5~ números enteros ~N (1 \le N \le 10^5 )~, ~A (1 \le A \le 10^9 )~, ~M (1 \le M \le 10^3 )~, ~B (1 \le B \le 10^3)~ y ~K (0 \le K \le 10^{14})~, que representan la cantidad de cajas que hay, el máximo de galletas por cada caja, la cantidad que le pagan por cada caja que tenga ~A~ galletas, la cantidad que le pagan por cada galleta en la caja con la menor cantidad de galletas y la cantidad de galletas que tiene por acomodar, respectivamente.

En la segunda línea ~N~ números enteros ~G_i (0 \le Gi \le A)~ que representan la cantidad de galletas que hay en cada caja.

Salida

La cantidad máximo de dinero que puede conseguir Juanito.

Ejemplo A

Entrada

3 5 10 1 5
1 3 1

Salida

12

Explicación.- Si Juanito agrega ~1~ galleta en la primera caja, ~2~ galletas en la segunda caja y ~1~ galleta en la tercer caja entonces la cantidad que tendría al final las cajas serían ~2~, ~5~ y ~2~, la menor cantidad de galletas en todas las cajas es ~2~ y la cantidad de cajas con la cantidad máxima permitida es ~1~ entonces el pago sería: la menor cantidad de galletas que hay en todas las ~cajas = 2~ multiplicado por ~B = 1~, más, la cantidad de cajas que tienen ~A~ galletas = ~1~ multiplicado por ~M = 10~ quedando el cálculo de la siguiente manera: ~2 * 1 + 1 * 10~ = ~2 + 10~ = ~12~.

Ejemplo B

Entrada

3 5 10 1 339
1 3 1

Salida

35

Explicación.-Si Juanito agrega ~4~ galletas en la primer caja, ~2~ galletas en la segunda caja y ~4~ galleta en la tercer caja entonces la cantidad que tendría al final las cajas serían ~5~, ~5~ y ~5~, la menor cantidad de galletas en todas las cajas es ~5~ y la cantidad de cajas con la cantidad máxima permitida es ~3~ entonces el pago sería la menor cantidad de galletas que hay en todas las ~cajas = 5~ multiplicado por ~B = 1~, más, la cantidad de cajas que tienen ~A~ galletas igual a ~3~ multiplicado por ~M = 10~ quedando el cálculo de la siguiente manera: ~5 * 1 + 3 * 10= 5 + 30 = 35~.

Subtareas

Subtarea 1 con un valor de 10 puntos.
~K = 0, N \le 1,000~ y Todos los valores de las cajas son diferentes
Subtarea 2 con un valor de 20 puntos.
~K = 0 y N \le 1,000~.
Subtarea 3 con un valor de 30 puntos.
~K = 1 y N \le 1,000~.
Subtarea 4 con un valor de 40 puntos.
~1 \le N \le 10^5~
~1 \le A \le 10^9~
~0 \le G_i \le A~
~1 \le M, C \le 10^3~
~0 \le K \le 10^{14}~

NOTA:

Cada subtarea contiene un conjunto de casos de prueba, se te darán los puntos siempre y cuando tu programa resuelva todos los casos de la subtarea.