Una benzinera massa llunyana P23800

Les $n+1$ ciutats $c_0, \dots, c_n$ estan connectades consecutivament per una única carretera. Voleu anar des de $c_0$ fins a $c_n$, parant com a molt $p$ vegades per omplir el dipòsit del cotxe. Només hi ha betzineres a les ciutats, no en els trams intermedis. La longitud de cadascun dels $n$ trams és $\ell_0, \dots, \ell_{n-1}$. Quina autonomia mínima ha de tenir el vostre cotxe? Suposeu que comenceu amb el dipòsit ple.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i $p$, seguits de $n$ naturals $\ell_0, \dots, \ell_{n-1}$. Suposeu $1 \le n \le 10^5$, $0 \le p \le n - 1$, i $1 \le \ell_i \le 10^4$.

Sortida

Per a cada cas, escriviu l’autonomia mínima que ha de tenir un cotxe per poder arribar fins a $c_n$ sortint de $c_0$ fent com a màxim $p$ parades per omplir el dipòsit.

Pista

Considereu una versió decisional d’aquest problema.