Tarongers P30103

El carrer on viu el professor Oak té diversos tarongers. Algun veí desconegut però amb evidents problemes psicològics ha demanat que se’n treguin les taronges. Com que la petició és totalment absurda, l’ajuntament ha decidit fer-ne cas. Podeu calcular el màxim nombre de taronges que es podran treure?

Suposeu aquest model: Hi ha $n$ tarongers en fila. El taronger $i$-èsim té $t_i$ taronges. Aniran a treure les taronges $m$ treballadors municipals, i tots i cadascun d’ells treurà totes les taronges d’exactament un taronger. Per evitar que els treballadors es distreguin xerrant entre ells, hauran d’estar separats per almenys un taronger.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i $m$, seguides de les $t_i$, totes entre 0 i $10^5$. Suposeu $1 \le n \le 1000$, $m \ge 0$ i $2m - 1 \le n$.

Sortida

Per a cada cas, escriviu el màxim nombre de taronges que es podran treure.

Pista

La solució esperada té cost $\Theta(n \cdot m)$.