Laura y el Robot
Laura tiene elementos en una línea. Los artículos están numerados consecutivamente por números del al de tal manera que el artículo más a la izquierda tiene el número , el artículo más a la derecha tiene el número . Cada artículo tiene un peso, el i-ésimo artículo pesa 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:
Toma el elemento más a la izquierda con el brazo izquierdo y gasta • unidades de energía ( es el peso del elemento más a la izquierda, es algún parámetro). Si la acción anterior era la misma (izquierda), entonces el robot gasta unidades de energía adicionales;
Toma el artículo más a la derecha con el brazo derecho y gasta • unidades de energía ( es el peso del artículo más a la derecha, es algún parámetro). Si la acción anterior fue la misma (brazo derecho), entonces el robot gasta 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 , , , , ( ; ). La segunda línea contiene enteros , ,..., ().
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 = , 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 • + • + • = 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 (•) + (•) + (•) + (• + ) = unidades de energía.
Comments