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 \le s \le 10$, $1 \le n \le 10^4$, i que cada cost es troba entre 1 i $10^4$.

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.