Laura y el Robot


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal

Laura tiene n elementos en una línea. Los artículos están numerados consecutivamente por números del 1 al n de tal manera que el artículo más a la izquierda tiene el número 1, el artículo más a la derecha tiene el número n. Cada artículo tiene un peso, el i-ésimo artículo pesa w_i kilogramos.

Laura necesita recolectar todos estos elementos, sin embargo, no lo hará sola. Utiliza su nuevo robot. El robot tiene dos brazos diferentes: el izquierdo y el derecho. El robot puede realizar consecutivamente las siguientes acciones:

  1. Toma el elemento más a la izquierda con el brazo izquierdo y gasta w_il unidades de energía (w_i es el peso del elemento más a la izquierda, l es algún parámetro). Si la acción anterior era la misma (izquierda), entonces el robot gasta Q_l unidades de energía adicionales;

  2. Toma el artículo más a la derecha con el brazo derecho y gasta w_jr unidades de energía (w_j es el peso del artículo más a la derecha, r es algún parámetro). Si la acción anterior fue la misma (brazo derecho), entonces el robot gasta Q_r unidades de energía adicionales;

Naturalmente, Laura quiere programar el robot de manera que gaste la menor cantidad de energía posible. Te pidió que resolvieras este problema. Su tarea es encontrar la cantidad mínima de unidades de energía que gasta el robot para recolectar todos los artículos.

Entrada

La primera línea contiene cinco números enteros n, l, r, Q_l, Q_r (1 \leq n \leq 10^5; 1 \leq l, r \leq 100; 1 \leq Q_l, Q_r \leq 10^4). La segunda línea contiene n enteros w_1, w_2,..., w_n (1 \leq w_i \leq 100).

Salida

En una única línea, escriba un solo número: la respuesta al problema.

Ejemplo de Entrada 1

3 4 4 19 1
42 3 99

Ejemplo de Salida 1

576

Ejemplo de Entrada 2

4 7 2 3 9
1 2 3 4

Ejemplo de Salida 2

34

Explicación

Considere el primer ejemplo. Como l = r, podemos tomar un elemento por turnos: primero del lado izquierdo, luego del derecho y el último elemento del lado izquierdo. En total el robot gasta 442 + 499 + 43 = 576 unidades de energía.

En el segundo ejemplo. La solución óptima es tomar un elemento de la derecha, luego uno de la izquierda y dos elementos de la derecha. En total, el robot gasta (24) + (71) + (23) + (22 + 9) = 34 unidades de energía.


Comments

There are no comments at the moment.