Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy. Stačí, že pôjdeš na stránku nášho testovača a budeš riešiť sadu Úvod do programovania. Každou z úloh Číslo, Zámena, Obdĺžnik 1 si vieš nahradiť 5 bodov z tejto úlohy. Pomôcť si vieš Python tutoriálom, ktorý sme pre teba nachystali. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na testovači.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Maťovi na [email protected]

Adam si na desiatu spravil masívnu, $n$ centimentrov dlhú bagetu. Potom ale zistil, že sa mu celá nezmestí do ruksaku. Rozhodol sa, že z nej aspoň vyreže úsek dlhý $k$ cm a ten už zbalí bez problémov. Rozloženie surovín v bagete ale nie je rovnomerné a na niektorých miestach chutí lepšie ako na iných. Adam sa preto rozhodol, že si vyberie taký úsek, ktorý chutí najlepšie.

Úloha

Na vstupe dostanete čísla $n$, $k$ a popis bagety, teda pre každý centimetrový dielik bagety dostanete na vstupe jedno celé číslo, jeho chuť. Chuť vybraného úseku bagety je súčet chutí dielikov, z ktorých sa skladá. Vašou úlohou je vypísať chuť najchutnejšieho súvislého úseku dĺžky presne $k$.

Pozor, vami vybraný úsek nemôže byť kratší ako $k$ centimetrov, bez ohľadu na to ako nechutný by bol. Adam by tak totiž ostal hladný.

Formát vstupu

Na prvom riadku vstupu sú dve čísla $n$ a $k$ ($1\leq k\leq n \leq 10^6$) – pôvodná dĺžka bagety a dĺžka úseku, ktorý z nej máte vyrezať.

Na druhom riadku je $n$ medzerou oddelených čísel $c_1$ až $c_n$, chuť jednotlivých dielikov. Platí, že $-10^9\leq c_i\leq10^9$.

Formát výstupu

Na jediný riadok výstupu vypíšte číslo $x$ – chuť najchutnejšieho súvislého úseku dĺžky $k$ cm.

Hodnotenie

Vaše riešenie bude testované na 5 sadách vstupov, za každý môžete získať 3 body. Pre prvé dve sady platí, že $n \leq 1\,000$.

Príklad

7 3
-2 5 7 3 9 -10 14

19