Imposto

Uma construtora especializada em condomínios de alto padrão está desenvolvendo o projeto de um condomínio ao redor de um lago. As casas serão construídas em lotes de tamanhos distintos, mas todos os lotes serão às margens do lago. Adicionalmente, cada lote terá exatamente dois vizinhos no condomínio: um à esquerda e um à direita.

Projeto indicando os tamanhos dos lotes (em unidades de área) no novo condomínio.

As terras ao redor do lago pertencem à companhia, e esta deve dividir as terras em lotes. No entanto, a prefeitura da cidade tem uma regra curiosa sobre partilha de terra, de forma a desencorajar a formação de lotes pequenos:

1) terrenos podem ser dividos usando uma seqüência de divisões de terras;
2) uma operação de divisão de terra divide um terreno em exatamente duas partes;
3) para cada operação de divisão de terra, um imposto de divisão de terra deve ser pago.

Denotando por T a área do maior terreno resultante de uma divisão de terra, o valor do imposto de divisão a ser pago é T × A, onde A é a alíquota do imposto de divisão de terras, estabelecida anualmente pela prefeitura. Note que devido à regra (2), para dividir um terreno em N lotes, N-1 operações de divisão de terra devem ser efeturadas, de forma que N-1 pagamentos devem ser feitos para a prefeitura.

Por exemplo, considerando a figura acima, se a alíquota de divisão é 2,50, e a primeira divisão separa o lote de 500 unidades de área dos lotes remanescentes, o imposto de divisão de terra a ser pago por esta primeira divisão é 2,50 × (100 + 300 + 200 + 100 + 100). Se a divisão de terra seguinte separar o conjunto formado pelo lote de 300 unidades e pelo lote de 100 unidades dos lotes remanescentes, um imposto adicional de 2,50 × (100 + 100) deve ser pago, e assim por diante. Note ainda que algumas divisões de terra não são possíveis, devido à regra (2). Por exemplo, após a primeira divisão de terra mencionada no exemplo acima, não é possível efetuar uma divisão de terras para separar o conjunto formado pelo lote de 300 unidades e pelo lote de 200 unidades dos demais lotes, pois mais de duas partes resultariam desta divisão.

Tarefa

Dados o valor corrente da alíquota do imposto de divisão e as áreas de todos os lotes ao redor do lago, você deve escrever um programa para determinar o menor valor total possível a ser pago como imposto de divisão de terras de modo a dividir as terras de acordo com o projeto do condomínio.

Entrada

A entrada é composta de vários casos de teste. A primeira linha de um caso de teste contém um número inteiro N e um número real A, indicando respectivamente o número de lotes (1 ≤ N ≤ 200) e a alíquota de divisão (com precisão de dois dígitos, 0 < A ≤ 5.00). A segunda linha contém N inteiros X[i], representando as áreas de lotes contíguos no projeto de condomínio (0 < X[i] ≤ 500, com 1 ≤ i ≤ N); adicionalmente, X[k] é vizinho de X[k+1] para 1 ≤ k ≤ N-1, e X[N] é vizinho de X[1]. O final da entrada é indicado por N = A = 0.

Os dados de entrada devem ser lidos da entrada padrão (teclado)

Exemplo de entrada

4 1.50
2 1 4 1
6 2.50
300 100 500 100 100 200
0 0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A segunda linha deve conter o valor total mínimo do imposto de divisão, como um número real com precisão de dois dígitos. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

A saída deve ser feita na saída padrão (tela)

Exemplo de saída

Teste 1
13.50

Teste 2
4500.00

Restrições

0 ≤ N ≤ 200 (N = 0 apenas para indicar o fim da entrada)
0 < A ≤ 5.0 (A = 0 apenas para indicar o fim da entrada)