Saltant amunt P57741

En un videojoc es comença a la part més baixa d’una escala, i cal anar saltant cap amunt fins a sortir per dalt de l’escala. Cada esglaó té un cert cost de trepitjar-lo. L’objectiu és minimitzar la suma del cost total de pujar les escales.

La gràcia del joc és que, en general, es pot saltar més d’un esglaó de cop. Un enter s limita quant es pot saltar cap amunt: si l’últim salt ha estat de j esglaons, en el pas següent només es poden saltar entre 1 i s + 1 − j esglaons. Per exemple, si s = 5 i l’últim salt ha estat de 4 esglaons, ara només se’n podran saltar 1 o 2.

Podeu calcular el cost mínim de pujar les escales? No cal trepitjar l’últim esglaó, podeu sortir saltant-hi per sobre.

Entrada

L’entrada consisteix en diversos casos, cadascun amb s i el nombre d’esglaons n, seguits del cost de cada esglaó, de baix a dalt. Suposeu 1 ≤ s ≤ 10, 1 ≤ n ≤ 10⁴, i que cada cost es troba entre 1 i 10⁴.

Sortida

Per a cada cas, escriviu el cost mínim de superar el joc. Inicialment us trobeu al primer esglaó (del qual heu de pagar el cost), i teniu dret a saltar entre 1 i s esglaons.