4. Sekanie bagety

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

Input:

7 3
-2 5 7 3 9 -10 14

Output:

19

Najchutnejší úsek, ktorý môže Adam z bagety vyrezať obsahuje 3, 4 a 5 centimeter s celkovou chuťou \(7+3+9 = 19\). Zvyšné úseky, napríklad 2 až 4 centimeter s chuťou 15 alebo 5 až 7 centimeter s chuťou 13, nie sú natoľko chutné.