Simulare🎅🏼🎄 | planor

Un planor este lansat pe un teren format din $N$ parcele a câte un km, numerotate de la 1 la $N$, dispuse liniar. Planorul este lansat de la începutul parcelei $X$, de la înălțime zero. El planează peste cel mult $K$ parcele, $K \leq N$, în sensul crescător al numărului de parcelă, iar apoi se oprește.

Fiecare parcelă dispune de curenți verticali, care fie înalță, fie coboară planorul. Pentru fiecare parcelă se cunosc numărul de metri cu care planorul își modifică înălțimea pe parcursul traversării acelei parcele (să numim acest număr diferență de nivel). Acest număr poate fi pozitiv, dacă el câștigă în înălțime, sau negativ, dacă pierde în înălțime.

Cerințe

Date fiind numărul $N$ de parcele, $K$ - numărul maxim de parcele pe care le poate parcurge planorul ce pornește de la înălțime zero, precum și diferențele de nivel corespunzătoare fiecăreia dintre cele $N$ parcele să se rezolve următoarele 3 cerințe:

1. înălțimea maximă la care ajunge planorul, dacă pleacă din prima parcelă și parcurge cel mult K parcele (dar cel puțin una);
2. înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă $X$ de lansare și după ce parcurge exact K parcele;
3. înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă $X$ de lansare și parcurge cel mult K parcele (dar cel puțin una).

Date de intrare

Fișierul de intrare planor.in conține pe prima linie numerele $C$, $N$ și $K$, reprezentând numărul cerinței (1, 2 sau 3), numărul de parcele și respectiv numărul maxim de parcele parcurse. A doua linie conține $N$ numere, reprezentând, în ordinea de la 1 la $N$, diferențele de nivel pentru cele $N$ parcele. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire planor.out va conține o singură linie pe care va fi scris un singur număr, răspunsul la cerința $C$ din fișierul de intrare.

Restricții și precizări

• $1 \leq K \leq N \leq 200 \ 000$;
• $-200 \ 000 \leq$ diferențele de nivel $\leq 200 \ 000$;
• Planorul poate ajunge la înălțime negativă în orice moment al zborului;
• Pentru $12$ puncte, $C = 1$;
• Pentru $4$ puncte, $C=2$ și $1 \leq N \leq 5 \ 000$;
• Pentru $16$ puncte, $C=2$ și $10 \ 000 \leq N \leq 200 \ 000$;
• Pentru $20$ de puncte, $C=3$ și $1 \leq N \leq 5 \ 000$;
• Pentru $48$ de puncte, $C=3$ și $10 \ 000 \leq N \leq 200 \ 000$.

Exemplul 1

planor.in

1 14 4
4 -5 3 -2 6 3 -2 -1 4 3 6 -4 2 3

planor.out

4

Explicație

Plecând de la parcela $1$ de la înălțime $0$ și zburând o singură parcelă către dreapta, planorul va ajunge la înălțimea $4$, care este maximă posibil.

Exemplul 2

planor.in

2 14 4
4 -5 3 -2 6 3 -2 -1 4 3 6 -4 2 3

planor.out

12

Explicație

Plecând de la parcela $8$ de la înălțime $0$ și zburând patru parcele către dreapta, planorul va ajunge la înălțimea $12$. Aceasta este înălțimea maximă posibilă.

Exemplul 3

planor.in

3 14 4
4 -5 3 -2 6 3 -2 -1 4 3 6 -4 2 3

planor.out

13

Explicație

Plecând de la parcela $9$ de la înălțime $0$ și zburând trei parcele către dreapta, planorul va ajunge la înălțimea $13$. Aceasta este înălțimea maximă posibilă.