Descrição
Renato gosta muito de geometria e acaba de achar alguns palitos em seu quarto. Ele está tentando utilizar esses palitos de forma a fazer um polígono com o maior número de lados possíveis.
Para montar o polígono, Renato não quer cruzar os palitos; ou seja, os palitos devem se tocar apenas nas pontas. Ele também não quer quebrar nenhum palito, de forma que todos os palitos que forem usados devem manter sua medida original.
Se, por exemplo, os palitos têm medidas 3, 4 e 5, é possível utilizar todos os três palitos para formar um triângulo. Mas se as medidas são 1, 1, 1 e 5, é possível formar um triângulo com três lados iguais a 1 mas não é possivel formar um polígono com todos os 4 palitos.
Você consegue ajudar Renato a descobrir qual é o maior número de palitos que ele consegue usar?
Entrada
A primeira linha contém apenas um inteiro N que indica o número de palitos. A segunda linha possui N inteiros indicando as medidas dos palitos.
Saída
Se programa deve imprimir uma única linha, contendo um único inteiro, o maior número de lados que o polígono pode ter seguindo as restrições do enunciado. Se não for possível formar nenhum polígono usando os palitos, imprima 0.
Restrições
• 3 ≤ N ≤ 100000
• As medidas dos palitos são inteiros positivos menores ou iguais a 10000
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
4 |
3 |
|
3 |
0 |
|
3 |
3 |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por Erich Rodrigues | Competição: OBI 2013, Nível 1, Fase 2