Rede de serviço
Há estações conectadas por estradas não direcionadas. Existe exatamente um caminho simples pelas estradas entre cada par de estações. Cada estrada tem um custo positivo de travessia.
Uma equipe deve realizar serviços de transporte. Cada serviço liga duas estações diferentes e pode ser realizado em qualquer sentido: a equipe começa em uma extremidade e termina na outra, usando um veículo próprio daquele serviço. Serviços diferentes podem ter as mesmas extremidades. Cada estação participa de pelo menos um serviço.
A equipe deve começar em uma estação de sua escolha, realizar cada serviço exatamente uma vez e terminar na estação inicial. A ordem e o sentido dos serviços são livres. A realização de um serviço não tem custo para a equipe, não conta como travessia das estradas e não permite parar em estações intermediárias.
Entre serviços, a equipe pode percorrer as estradas, pagando o custo de cada travessia. Uma estrada pode ser percorrida várias vezes. Percorrer uma estrada não realiza nenhum serviço, mesmo que suas extremidades coincidam com as de um serviço.
Qual é o menor custo total das travessias de estradas?
Input
A primeira linha contém e (, ).
Output
Imprima um inteiro: o menor custo total.
Samples
Sample 1
Input
4 2 1 2 2 2 3 5 3 4 3 1 2 3 4
Output
15
Uma solução começa em , realiza o serviço até , vai pela estrada até por custo , realiza o serviço até e volta pelas estradas a por custo .