Problema A - Agente 073

O Tiago Vínculo, também conhecido por agente 073, é um super agente super secreto conhecido no mundo da espionagem pelas suas magníficas missões.

Vínculo foi capturado por Doutor Sim, um super vilão que ambiciona dominar o mundo. Para escapar a Sim, o agente 073 terá que o vencer num desafio, ou será devorado por crocodilos. O desafio consiste no seguinte:

• O Doutor Sim começa por escolher um número negativo.
• De seguida escreve, num quadro, uma sequência de N números positivos ou negativos, em que os negativos são todos iguais ao número escolhido no passo anterior.
• Há uma tômbola com bolas, numeradas, da qual Doutor Sim irá extrair uma, que tem o número K.
• Dado o número presente na bola, K, Tiago Vínculo pode trocar o sinal (ou seja, multiplicar por -1) de até K números no quadro.
• Vínculo escolhe então uma subsequência contígua no quadro e calcula a sua soma. Uma subsequência contígua corresponde a um conjunto de números seguidos da sequência (vejam o exemplo seguinte para mais clarificarem a definição).
• Se dada a sequência inicial e o valor K não for possível encontrar uma subsequência contígua com soma maior que a de Vínculo no passo anterior, Doutor Sim liberta-o.

Vejamos um exemplo. Suponhamos que o Doutor Sim escolhe o número -10 e escreve a seguinte sequência de N = 9 números: [5, 6, -10, -10, 5, 5, -10, 5, 5]. Agora, suponham que o número extraído é K = 0, ou seja, o Vínculo não pode trocar o sinal a qualquer número. Neste caso, a subsequência contígua de maior soma é a subsequência [5, 6], de soma 11. Outras subsequências contíguas possíveis seriam a subsequência [6, -10, -10] de soma -14, ou a subsequência [5, -10, 5] de soma 0, mas a sua soma não é a máxima.

Agora suponham que o número extraído é K = 1, então o trocar o sinal do último -10 da sequência, obtendo a sequência [5, 6, -10, -10, 5, 5, 10, 5, 5], podemos obter a subsequência contígua [5, 5, 10, 5, 5] cuja soma é 30. Podem verificar que não há melhor estratégia, se trocarmos o sinal do primeiro -10 ficamos com [5, 6, 10, -10, 5, 5, -10, 5, 5] e a maior subsequência contígua seria [5, 6, 10] de soma 21, se trocássemos ao segundo -10 teríamos a sequência [5, 6, -10, 10, 5, 5, -10, 5, 5] e a maior subsequência contígua seria [5, 6, -10, 10, 5, 5] de soma 21.

O teu objetivo é calcular o valor da maior soma que Tiago Vínculo pode obter, para garantir que não é devorado por crocodilos, salvando o mundo uma vez mais.

O Problema

Dados inteiros N e K e uma sequência de N inteiros onde todos os valores negativos são iguais, calcular a forma de trocar o sinal a no máximo K elementos que obtém a maior soma de uma subsequência contígua.

Input

Nota: este problema contém múltiplos inputs por caso de teste! Isto significa que terás de devolver a resposta para vários conjuntos de medições com o teu programa.

A primeira linha contém um inteiro, T, que representa o número de inputs. Seguem-se T conjuntos de inputs onde cada um tem o seguinte formato:

Primeiro contêm uma linha com dois inteiros separados por espaços, N que representa o tamanho da sequência, e K, que representa o número máximo de elementos aos quais podemos trocar o sinal.

Segue-se uma linha com N inteiros separados por espaços, onde o i-ésimo representa o i-ésimo valor da sequência, S_i.

Notem que todos os números negativos da sequência dada serão iguais.

Output

Para cada um dos T inputs deves imprimir uma linha contendo um inteiro, a soma da subsequência contígua máxima que é possível de se obter depois de trocar o sinal a até K elementos.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Input do Exemplo 1

2
9 0
5 6 -10 -10 5 5 -10 5 5
9 1
5 6 -10 -10 5 5 -10 5 5

Output do Exemplo 1

11
30

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

3
5 0
-5 -5 -5 -5 -5
5 0
6 -5 1 5 -5
5 1
6 -5 1 5 -5

Output do Exemplo 2

0
7	
17