/*
 * Luata de la http://infoarena.ro/problema/secv2.
 */

/*
Gigel s-a decis sa devina olimpic la informatica, poate asa va reusi sa-si rezolve singur problemele, si nu va mai cere ajutorul vostru! La ora de informatica, profesoara lui i-a dat sa rezolve problema secventei de suma maxima: "Gigele, eu iti dau un sir de N numere intregi, iar tu trebuie sa gasesti o secventa (adica un subsir de numere care apar pe pozitii consecutive in sirul initial) cu suma elementelor maxima!". Dupa vreo 30 de minute, Gigel s-a ridicat mandru si a zis: "Am gasit algoritmul de complexitate optima, doamna profesoara!"
Ca tema pentru acasa Gigel are de rezolvat aproape aceeasi problema: trebuie sa gaseasca secventa de suma maxima de lungime cel putin K!

Date de intrare
Fisierul de intrare secv2.in contine pe prima linie numerele N si K, separate prin spatiu. Pe cea de a doua linie se afla elementele sirului separate prin cate un spatiu.

Date de iesire
Fisierul de iesire secv2.out trebuie sa contina o singura linie cu trei numere: pozitia de inceput si de sfarsit a secventei de suma maxima de lungime cel putin K si suma secventei.

Restrictii si precizari
    * 1 <= K <= N <= 50.000
    * Elementele din vector sunt numere intregi din intervalul [-25.000, 25.000]

Exemplu

secv2.in
8 3
0 -6 2 1 4 -1 3 -5

secv2.out
3 7 9
*/

#include <stdio.h>

#define IN_FILE "secv2.in"
#define OUT_FILE "secv2.out"

#define MAX_N 50000
#define MIN_SUM -1250000001

int N, K;
int numere[MAX_N + 1];

int max(int n1, int n2)
{
	return ((n1 > n2) ? n1 : n2);
}

int main(void)
{
	int i, j, sum_last_k;
	int max_sum, begin, end;	//4 bytes signed sunt suficienti pentru suma maxima a 50.000 de numere din intervalul specificat
	int S[MAX_N + 1], len[MAX_N + 1];	//indexam de la 1 ca sa fie mai coerent

	FILE *fin, *fout;

        fin = fopen(IN_FILE, "r");
        fscanf(fin, "%d %d\n", &N, &K);
        for (i = 1; i <= N; i++)
        {
                fscanf(fin, "%d ", numere+i);
        }
        fclose(fin);


	/*
	 * O idee simpla, de complexitate O(n*n - n*k):
	 * Sa gasesc cea mai buna suma de lungime k - O(n) 
	 * Sa gasesc cea mai buna suma de lungime k+1 - O(n)
	 * ..........................................
	 * Sa gasesc cea mai buna suma de lungime n - O(n) 

	 * Dar pot gasi si o solutie de complexitate O(n)
	 */

	/* Initializari */
	len[K] = K;
	S[K] = 0;
	for (i = 1; i <= K; i++)
		S[K]+= numere[i];
	max_sum = MIN_SUM;

	/* Algoritmul */
	for (i = K + 1; i <= N; i++)
	{
		/* Gasim S[i] */
		if (len[i-1] == K)
		{
			/* Daca lungimea sirului care da S[i] maxima este chiar k, inseamna ca nu avea rost sa includ niciunul din elementele de dinaintea sirului (ar fi contribuit negativ !)
			 * Asta inseamna ca nu are rost sa le includ nici in calculul S[i+1]
			 */
			if ( (S[i-1] + numere[i]) > (S[i-1] + numere[i] - numere[i-K]) )
			{
				len[i] = K + 1;
				S[i] = S[i-1] + numere[i];
			}
			else
			{
				len[i] = K;
				S[i] = S[i-1] + numere[i] - numere[i-K];
			}
		}
		else
		{
			/* */
			if (numere[i - K] < 0)
			{
				sum_last_k = 0;
				for (j = i - K + 1; j <= i; j++)
					sum_last_k+= numere[j];
				if (sum_last_k > S[i - 1] + numere[i])
				{
					S[i] = sum_last_k;
					len[i] = K;
				}
				else
				{
					S[i] = S[i-1] + numere[i];
					len[i] = len[i-1] + 1;
				}
			}
			else
			{
				S[i] = S[i-1] + numere[i];	//aici ar putea fi eliminata un pic redundanta
				len[i] = len[i-1] + 1;
			}
		}

		/* Verificam daca S[i] este maxim */
		if (S[i] > max_sum)
		{
			max_sum = S[i];
			end = i;		
			begin = i - len[i] + 1;	
		}
	}

	

        fout = fopen(OUT_FILE, "w");
        fprintf(fout, "%d %d %d\n", begin, end, max_sum);
        fclose(fout);

        return 0;
}