Vacances organitzades P43543

Statement

En unes vacances organitzades d’ $n$ dies de durada es pot fer una excursió cada dia. La satisfacció que produeix l’excursió $i$ -èsima es $s_i$ . Volem maximitzar la suma total de satisfaccions, amb una sola restricció: no es poden fer més de $k$ excursions seguides.

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters, cadascun amb $n$ , $k$ , i les $n$ satisfaccions $s_i$ . Podeu suposar $2 \le n \le 10^4$ , $1 \le k \le \min(n - 1, 10)$ , i $1 \le s_i \le 10^9$ .

Sortida

Per a cada cas, escriviu la màxima satisfacció possible.

Public test cases

Input

2 1  10 20
5 2  1 1 1 1 1
7 2  1000000000 1 1000000000 1 1000000000 1 1000000000
9 3  42 20 42 23 20 42 23 42 42

Output

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++