Unirea pentru Performanta - Online | Euro 2024

Cerință

Lensu este în celălalt capăt al lumii însă vrea să ajungă la finala Euro 2024 din Germania. El are în drum $N$ orașe și inițial se află în orașul $1$ scopul lui fiind să ajungă în orașul $N$, mai exact, stadionul din Berlin. El are la dispoziție $z$ zile să ajungă pentru a nu pierde finala, iar în fiecare zi trebuie să se oprească într-un oraș pentru a se odihni. Fiecare oraș are un cost $v_i$ lei de staționare, $i \ (1 \leq i \leq N)$, în cazul în care Lensu vrea sa se oprească la un hotel de acolo. De la o zi la alta, el poate parcurge maxim $k$ orașe, adică dacă este într-o zi în orașul $x$, orașul cel mai îndepărtat în care acesta se va putea caza ziua următoare este orașul $x+k$.

De fiecare dată când se oprește într-un oraș Lensu va scoate de la bancă aceeași sumă de bani să plătească cazarea, pentru a îi fi mai ușor.
Determinați care este numărul de bani minim pe care trebuie să îl scoată de la bancă de fiecare dată când se oprește într-un oraș pentru a ajunge la timp la finală.

Date de intrare

Pe prima linie a fișierului de intrare euro.in se găsesc numerele naturale $N$, $z$ și $k$.
Pe urmatoarea linie a fișierului de intrare euro.in se gasesc cele $N$ numere naturale $v_i$, separate printr-un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire euro.out se va găsi un singur număr natural, numărul de bani minim pe care Lensu trebuie să îl scoată de la bancă de fiecare dată când se oprește într-un oraș.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $1 \leq v_i \leq 1 \ 000 \ 000$;
• $1 \leq z \leq N$;
• $1 \leq k \leq 200 \ 000$;
• Lensu se va caza neapărat în orașul $1$ și în orașul $N$.
• Dacă Lensu scoate de la bancă $x$ bani și staționarea costă $y$ bani, unde $x \geq y$, atunci el poate staționa în orașul respectiv
• În cazul în care Lensu scoate $x$ bani și staționarea costă $y$ bani, unde $x > y$, banii rămași după ce se cazează nu se mai iau în considerare
• În cazul în care Lensu nu poate ajunge la finală se va afișa $-1$

Exemplul 1

euro.in

10 4 3
1 3 4 2 4 5 3 2 3 1

euro.out

3

Explicație

Lensu staționează în 4 zile diferite, în orașele: $1$, $4$, $7$, $10$, numărul minim de bani pe care trebuie să îl scoată fiind $3$. ($3 > 1$, $3 > 2$, $3 = 3$, $3 > 1$)
Observație: Lensu nu putea să staționeze în orașul $5$ în a doua zi deoarece $5 - 1 > k$

Exemplul 2

euro.in

15 4 3
1 3 4 3 4 5 3 2 3 1 2 3 4 2 4

euro.out

-1

Explicație

Orice număr de bani ar scoate Lensu, acesta nu ajunge la finală deoarece trebuie să se oprească prea des.