castig

Ana şi Bogdan au participat la un concurs şi au obţinut premiul I, respectiv premiul al II-lea.
La concurs există $n$ premii, numerotate de la $1$ la $n$, în ordinea în care sunt aşezate pe masă.
Regulamentul concursului prevede că fiecare câştigător trebuie să aleagă exact $k$ premii aşezate pe poziţii consecutive. Fiindcă Ana are premiul I, ea poate să îşi aleagă prima premiile. Apoi Bogdan va alege şi el $k$ premii aşezate pe poziţii consecutive dintre cele rămase după ce a ales Ana.
Ana este foarte supărată pe Bogdan, aşa că ea urmăreşte ca Bogdan să câştige cât mai puţin, fără să o intereseze prea mult ce premii alege ea.

Cerinţă

Scrieţi un program care, cunoscând $n$, $k$ şi valorile celor $n$ premii, determină cel mai mic număr $val_{min}$, astfel încât Bogdan să nu poate selecta $k$ premii aşezate pe poziţii consecutive cu o valoare totală mai mare decât $val_{min}$.

Date de intrare

Fişierul de intrare castig.in conţine pe prima linie două numere naturale $n \ k$, reprezentând numărul total de premii şi respectiv numărul de premii consecutive pe care câştigătorii trebuie să le aleagă. Pe a doua linie se află $n$ numere naturale $v_1 \ v_2 \dots v_n$ reprezentând, în ordinea aşezării pe masă, valorile celor $n$ premii.

Date de ieşire

Fişierul de ieşire castig.out va conţine o singură linie pe care va fi scris numărul natural $val_{min}$, determinat conform cerinţei.

Restricții și precizări

• $3 \leq n \leq 100 \ 000$
• $1 \leq k \leq \frac{n}{3}$
• $1 \leq v_i \leq 10^9 \forall 1 \leq i \leq n$

Exemplul 1

castig.in

10 3
2 5 7 3 1 22 7 2 9 1

castig.out

15

Explicație

Dacă Ana alege premiile cu valorile $1 \ 22 \ 7$, secvenţa cea mai convenabilă pentru Bogdan este $5 \ 7 \ 3$ (deci $val_{min}$ este $15$).
Există şi alte alegeri bune pentru Ana $(22 \ 7 \ 2)$, dar $val_{min}$ rămâne acelaşi.