Etiquetas

Uma fita esticada horizontalmente é composta de N quadrados de dimensão 1 x 1, cada um deles contendo um número inteiro anotado. Temos também K etiquetas retangulares idênticas, de dimensão 1 x C, onde C é um inteiro. Nosso objetivo é colar todas as etiquetas sobre a fita de modo que a soma dos inteiros que não estiverem cobertos por nenhuma etiqueta ao final seja a máxima possível. Cada etiqueta deve ser colada na horizontal, ao longo da fita. Duas etiquetas não podem estar sobrepostas e cada quadrado da fita deve estar ou totalmente coberto por uma etiqueta, ou totalmente descoberto.

Entrada

A primeira linha da entrada contém três inteiros N, K e C, representando, respectivamente, o comprimento da fita, o número de etiquetas e o comprimento das etiquetas. A segunda linha da entrada contém N inteiros A indicando a sequência de números anotados nos quadrados da fita.

Saída

Seu programa deve imprimir uma linha contendo um inteiro indicando a soma máxima possível de inteiros descobertos na fita depois que todas as etiquetas sejam coladas seguindo as condições do enunciado.

Restrições

• 1 ≤ N ≤ 10000
• -10000 ≤ A ≤ 10000
• 1 ≤ K ≤ 10000
• 1 ≤ C ≤ 10000
• K\times C ≤ N

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo 10 pontos, os números no vetor estão ordenados crescentemente.
• Para um conjunto de casos de testes valendo outros 10 pontos, C=1.
• Para um conjunto de casos de testes valendo outros 20 pontos, K=1.
• Para um conjunto de casos de testes valendo outros 20 pontos, K,N ≤ 100.

Exemplos

12 2 3
1 22 4 -8 9 2 10 -1 5 5 32 -11

58
	

1 1 1
10000

0