Informática Iniciante- Semana 73

Teste da Árvore de Segmentos

Seu Madruga finalmente arrumou um emprego, é sua grande chance de pagar os 14 meses de aluguel que estão atrasados. Seu cargo é o de cortador de papel e o salário é excelente.

Madruga irá receber $N$ tiras retangulares de papel com $1$ $cm$ de largura e $C$ $cm$ de comprimento. As tiras devem ser colocadas uma ao lado da outra de forma que suas bases estejam alinhadas. A tarefa de seu Madruga será, com apenas um corte em linha reta, paralelo à base, fazer com que a soma das áreas das tiras cortadas seja igual a $A$ $cm^2$.

Veja a ilustração abaixo com $N = 5$ e as tiras com $5$, $3$, $6$, $2$ e $3$ $cm$ de comprimento, respectivamente, para um $A = 3$ $cm^2$.

Com um corte feito a uma altura de $4$ cm em relação a base, a área resultante, pintada de vermelho, é exatamente igual a $A$ $cm^2$. Sua tarefa é descobrir essa altura $H$ e ajudar Seu Madruga a se manter no emprego.

Entrada

Haverá diversos casos de testes. A primeira linha de cada caso inicia com dois inteiros $N$ $(1 \leq N \leq 10^5)$ e $A$ $(1 \leq A \leq 10^9)$. representando, respectivamente, a quantidade de tiras e a área resultante esperada. A próxima linha conterá $N$ inteiros, representando o comprimento $C_i$ $(1 \leq C_i \leq 10^4)$ de cada tira.

A entrada termina quando $C = A = 0$, a qual não deve ser processada.

Saída

Para cada caso, exiba uma única linha, a altura $H$ do corte que Seu Madruga deve fazer para que a soma da área das tiras cortadas seja igual a $A$ $cm^2$. Use $4$ casas decimais após o ponto.

Exiba ": D", caso nenhum corte seja necessário, ou "-.-" caso seja impossível.

Exemplos

ENTRADA	SAÍDA
5 3 5 3 6 2 3 4 14 2 5 2 5 0 0	4.0000 : D

Enviar solução: URI