Cruce de río.


Submit solution

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

Author:
Problem type
Allowed languages
C, C++, Java, JS, Pascal, Python, VB

El Granjero Juan está llevando su rebaño de N vacas (1 \leq N \leq 2,500) a través de las extensiones de su granja cuando él se encuentra bloqueado por un río. Se dispone de una sola balsa para transporte. GJ sabe que él debe estar en la balsa en todos los cruces y que añadir vacas a la balsa hace que ella atraviese más lentamente el río.

Cuando GJ está solo en la balsa, él puede cruzar el río en M minutos (1 \leq M \leq 1000). Cuando se añade la vaca i, toma M_i (1 \leq M_i \leq 1000) minutos más cruzar el río que con i-1 vacas (esto es un total de M+M_1 minutos con una vaca, M+M_1+M_2 con dos, etc.). Determine el tiempo mínimo que le toma al Granjero Juan atravesar todas las vacas a través del río (incluyendo el tiempo regresando para pasar más vacas).

Entrada

  • Línea 1: Dos enteros separados por espacio: N y M.
  • Líneas 2...N+1: La línea i+1 contiene un solo entero: M_i.

Ejemplo de Entrada

5 10  
3  
4  
6  
100  
1

Detalles de la Entrada: Hay 5 vacas. El Granjero Juan gasta 10 minutos para cruzar solo el río, 13 con una vaca, 17 con dos vacas, 23 con tres, 123 con cuatro y 124 con todas las cinco vacas.

Salida

En una sola línea el tiempo mínimo que le toma al Granjero Juan para atravesar el río con todas las vacas.

Ejemplo de Salida

50

Detalles de la Salida: El Granjero Juan puede cruzar primero el río con tres vacas (23 minutos), luego devolverse (10 minutos), y luego con las últimas dos (17 minutos). 23+10+17=50 minutos en total.


Comments

There are no comments at the moment.