Runda 2: Lepsza gra

Limit czasowy: 2 sekundy
Limit pamięciowy: 32 MB

Po wielu godzinach gry Alicja zauważyła, że "Pionki" są kompletnie bezsensowne. Nie dość, że dla każdego początkowego ustawienia łatwo stwierdzić kto ma strategie wygrywającą, to ruchy graczy nie mają żadnego wpływu na wynik gry! Ciekawiej już grać kartami w wojnę. Alicja bardzo lubi Boba, a jak wszyscy wiemy Bob spędził wiele czasu nad "Pionkami" wymyślając setki mniej lub bardziej wymyślnych strategii. Prawda o tej grze byłaby dla niego zbyt okrutna. Z tego powodu, Alicja zgodziła się przyznać Bobowi tytuł mistrza "Pionków" i zaproponowała nową grę - tym razem jednoosobową na punkty.

Podobnie jak w "Pionkach", planszę stanowi rząd ponumerowanych pól od 1 do n. Każde pole ma swoją wartość. Gracz zaczyna rozgrywkę pionkiem stojącym na polu o numerze k. Pojedynczy ruch to wybór kierunku (lewo lub prawo) i liczby pól, o którą ma przesunąć się pionek. Idąc w prawo z pola o numerze A na pole o numerze B do wyniku gry dodajemy wartości pól o numerach A, A+1, A+2,...,B-1,B. Idąc w lewo z pola o numerze A na pole o numerze B do wyniku gry dodajemy wartości pól o numerach A, A-1, A-2,...,B+1,B. Dopuszczalne są ruchy, w których A = B (wtedy gracz zdobywa liczbę punktów równą wartości pola o numerze A). Pionek nie może wyjść poza obręb planszy.

Alicja bardzo lubi tę grę, ale boi się, że jak będzie zbyt często wygrywać, to Bob znowu będzie chciał grać w "Pionki". Przydałby się jej program, który dla danego układu początkowego obliczy ile maksymalnie można zdobyć punktów wykonując co najwyżej m ruchów... Twoim zadaniem jest oczywiście pomóc Alicji.

Wejście

W pierwszej linii znajdują się 3 liczby całkowite n,k,m (1<=k<=n<=1000000, 0<=m<=1000000) oddzielone pojedynczym odstępem. W drugiej linii znajduje się n liczb całkowitych oddzielonych pojedynczym odstępem - są to wartości kolejnych pól planszy. Wartość bezwzględna każdej z tych liczb nie przekracza 1000000.

Wyjście

W pierwszej i jedynej linii Twój program powinien wypisać dokładnie jedną liczbę - maksymalny wynik w grze, który można uzyskać wykonując co najwyżej m ruchów.

Przykład

Dla danych wejściowych:

5 1 3
2 -2 4 3 -10

poprawną odpowiedzią jest:

21

Objaśnienie przykładu

Zaczynamy pionkiem na pierwszym polu.
Ruch 1: Idziemy z pola o numerze 1 na pole o numerze 4, zbierając 2-2+4+3 = 7 punktów.
Ruch 2: Idziemy z pola o numerze 4 na pole o numerze 3, zbierając 4+3 = 7 punktów.
Ruch 3: Idziemy z pola o numerze 3 na pole o numerze 4, zbierając 4+3 = 7 punktów.