Salões lotados

É época de carnaval e muitas pessoas estão alugando salões de festa para realizar suas festas. Devido à grande quantidade de salas alugadas, a Notável Organizadora de Incríveis Cerimônias, NOIC, enfrenta o seguinte problema: o espaço de festas do NOIC é uma construção circular, com vários salões de festa dentro dele, cada salão tendo uma porta para os salões vizinhos e uma porta para o exterior. Acontece que, devido ao alto custo de se ter uma entrada (porteiro, câmeras de segurança ligadas, estacionamento provisório, etc.) não há uma entrada para cada salão de festa. Isso faz com que um indivíduo qualquer tenha que usar a entrada de um outro salão e passar por outras salões até chegar a sua festa, o que gera um certo grau de desconforto para o indivíduo. Mais especificamente, o grau de desconforto de um indivíduo é a quantidade de salões por quais ele terá que passar antes de chegar na sua festa. Ademais, devido ao espírito do bloquinho de Carnaval, só se pode andar de salão em salão em um único sentido, e o NOIC decidiu que esse será o sentido horário.

Dado o número $N$ de salões de festa, quantas pessoas irão festejar em cada salão e a quantidade $K$ de entradas que o NOIC consegue bancar, calcule o mínimo desconforto geral (i.e. menor soma dos graus de desconforto individuais) se as entradas forem abertas nos melhores locais possíveis.

Entrada:

A primeira linha contém dois inteiros $N$ e $K$. As próximas N linhas contém um inteiro $v_i$ ($1\leq i\leq N$) - quantas pessoas vão festejar no salão $i$.

Saída:

Seu programa deve imprimir uma linha contendo o mínimo desconforto geral.

Limites:

• $1\leq N\leq 100$
• $1\leq K\leq 7$
• $1\leq v_i\leq 10^6$

Exemplo:

6 2
2
5
4
2
6
2

14

A NOIC pode ter entradas nas salas 2 e 5. 11 pessoas entram no salão 2, gerando um grau de desconforto igual a 8 para chegar nos salões 2, 3 e 4. 10 pessoas entram no salão 5, gerando um grau de desconforto igual a 6 para chegar nos salões 5, 6, e 1.

Para submeter a sua solução, use esse link