ratb

Управата на град Букурещ решила да продаде на търг по един билборд на всяка от n-те спирки по маршрута на автобусна линия 2006. За целта било направено проучване, с цел да се оцени месечната печалба, в румънски леи, която може да бъде получена от всеки билборд. За някои спирки, разположени на не много оживени места се оказало, че е възможно да няма печалба, а дори и загуба (отрицателна печалба!). За да продадат билбордовете на всяка цена, градската управа решила, че всеки инвеститор, който се интересува от подобна покупка, трябва да купи поне k  билборда, разположени на последователни спирки. Вашата задача е да определите последователността от билбордове, която трябва да купи един инвеститор, за да има максимална печалба. Ако не е възможно да се осигури печалба, то поне загубата да бъде колкото се може по-малка.

Задача

Определете максималната печалба, която може да се получи от k или повече последователни билбордове, както и да се посочат номерата на първия и последния билборд от последователността, за които се достига максималната печалба. Билбордовете са номерирани с числата от 1 до n.

Вход

Входният файл ratb.in съдъдържа на първия ред целите положителни числа n и k, разделени с интервал, а на втория ред от файла са записани n цели числа, разделени с интервали, представляващи очакваната печалба за всеки един от n-те билбордове.

Изход

Изходният файл ratb.out трябва да съдържа на първия ред търсената максимална печалба, а на втория ред номерата на първия и последния билборд, от последователността, за която се достига максималната печалба. Ако има повече от една последователности, за които се достига максималната печалба трябва да бъде изведена тази, която е по близка до началото на маршрута (номерът на първия билборд е минимален; ако има повече от едно решение с минималния начален номер, трябва да бъде изведено решението, което има най-малък номер на последния билборд).

Ограничения

Примери

ratb.in

ratb.out

ratb.in

ratb.out

10 3
23 -70 -73 82 -6 49 85 -118 37 26

210
4 7

7 2
-35 -12 -60 49 -80 -100 -20

-11
3 4

 

ratb.in

ratb.out

10 3
-100 10 10 10 -70 10 10 10 -50 -20

30
2 4

Ограничение за време: 0.1 секунди на тест

lect. drd. Radu Boriga
"Titu Maiorescu" University - Bucharest
Contact:r_boriga@yahoo.com

(Превод на български: Стоян Капралов)