Taxa
Uma empresa está construindo um condomínio de casas ao redor de um lago. As casas serão construídas em lotes de terra de diferentes tamanhos, mas todos os lotes serão às margens do lago. Além disso, cada lote de terra terá exatamente dois vizinhos no condomínio, um vizinho à direita e um vizinho à esquerda.
A empresa é dona de todo o terreno do condomínio e necessita dividir o terreno em lotes, de acordo com o projeto do condomínio. No entanto, a Prefeitura tem uma lei curiosa de imposto sobre divisão de terra, criada para inibir a criação de lotes de terra muito pequenos:
- um terreno pode ser dividido apenas usando uma sequência de
divisões de terreno ; - uma divisão de terreno é uma operação que divide um terreno em duas partes; e
- para cada divisão de terreno deve ser pago um imposto.
Por exemplo, considerando a figura acima, se o fator de divisão é 2.5 e a primeira divisão de terreno separa o lote com 500 unidades de área dos outros lotes, o imposto a ser pago nesta primeira divisão é 2.5 x (300+200+100+100+100). Se a próxima divisão de terreno separa dos lotes restantes o lote de 300 unidades junto com seu lote vizinho de 100 unidades, um imposto adicional de 2.5 x (300+100) deve ser pago; e assim por diante. Note também que algumas divisões de terra não são possíveis, devido a (2). Por exemplo, após a primeira divisão de terreno mencionada anteriormente não é possível fazer uma divisão para separar a área formada pelo lote de 300 unidades e o lote de 200 unidades da área formada pelos três lotes restantes, porque mais do que duas partes resultariam dessa operação.
Dadas as áreas de todos os lotes ao redor do lago e o valor corrente do fator de divisão, escreva um programa para determinar o menor valor de imposto total que deve ser pago para dividir a terra de acordo com o projeto de condomínio.
Entrada
A primeira linha contém um número inteiro N e um número real F, indicando respectivamente o número de lotes no condomínio e o fator de divisão (com precisão de dois dígitos). A segunda linha contém N números inteiros Xi, representando as áreas de lotes vizinhos no projeto do condomínio, para 1 ≤ i ≤ N, sendo que Xk é vizinho de Xk+1 para 1 ≤ k ≤ N-1, e XN é vizinho de X1.Saída
Seu programa deve produzir uma única linha na saída, contendo o valor mínimo do imposto a ser pago, como um número real com precisão de dois dígitos decimais.Restrições
- 1 ≤ N ≤ 200
- 0 ≤ F ≤ 5.00
- 0 < Xi ≤ 500, para 1 ≤ i ≤ N
Informações sobre a pontuação
- Em um conjunto de casos de teste somando 20 pontos, N ≤ 8
Exemplos
Entrada
4 1.50 2 1 4 1 |
Saída
13.50 |
Entrada
6 2.50 300 100 500 100 100 200 |
Saída
4500.00 |
