Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RNR_01_10 - Reklama na Times Square

Codziennie na Times Square wyświetlanych jest n reklam. Każda z nich musi trwać 1 jednostkę czasu. Postanowiłem wykupić dokładnie x emisji mojej reklamy w ciągu dnia. Chciałbym, aby w dowolnym przedziale k jednostek czasu moja reklama była wyświetlona co najmniej raz. Posiadam również statystyki ile osób ogląda reklamę w danej jednostce czasu.

Odpowiedz na pytanie, ile maksymalnie osób może zobaczyć moją reklamę?

Wejście

W pierwszej linii wejścia znajdują się trzy liczby całkowite n ∈ [1, 5000], k ∈ [1, n] oraz x ∈ [1, n], opisane w treści zadania.

W drugiej linii wejścia znajduje się n liczb całkowitych z przedziału [1, 109]. Liczba i-ta w kolejności określa ile osób ogląda reklamę w i-tej jednostce czasu.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile maksymalnie osób może zobaczyć moją reklamę.

Jeżeli wybranie x jednostek czasu, tak aby w dowolnym przedziale k jednostek czasu moja reklama była wyświetlona co najmniej raz, nie jest możliwe wypisz -1.

Przykład 1

Wejście:

11 3 4
19 1 22 10 1 5 50 8 10 99 100

Wyjście:

181

Wyjaśnienie do przykładu:

Optymalnym rozwiązaniem jest emisja reklamy w 3, 4, 7 i 10 jednostce czasu.

Przykład 2

Wejście:

8 2 3
2019 2 22 1 350 83 8 12

Wyjście:

-1

Dodane przez:Maciej Boniecki
Data dodania:2019-02-22
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Rak n Roll 1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.