Expedição de retorno
Uma expedição visitará todas as salas de uma árvore. Ela escolhe livremente uma sala inicial, que passa a ser a raiz. A visita a uma sala segue exatamente este procedimento:
- Ao entrar pela primeira vez, paga unidades de energia.
- Visita completamente cada subárvore filha, em uma ordem à sua escolha, sempre retornando a antes de iniciar a próxima.
- Depois de terminar todas as subárvores filhas, recebe unidades de energia e encerra a visita a .
O deslocamento pelas arestas não custa energia. Cada pagamento exige que haja energia suficiente naquele instante; a energia nunca pode ficar negativa. A recompensa de uma sala só é recebida no passo 3, inclusive para a raiz.
Qual é a menor energia inicial necessária, escolhendo tanto a raiz quanto as ordens das visitas?
Input
A primeira linha contém (). Cada uma das próximas linhas contém e (), na ordem dos vértices a . Cada uma das próximas linhas contém e (), uma aresta. Essas arestas formam uma árvore.
Output
Imprima a menor energia inicial necessária.
Samples
Sample 1
Input
3 5 0 1 6 4 0 1 2 1 3
Output
6
Comece em , visite e depois . A energia passa por durante os pagamentos e a recompensa não nula.