O arquipélago JOI é um pequeno país insular no oceano Pacífico. Há $N$ ilhas no arquipélago JOI, numeradas de $1$ a $N$.
A comunicação entre as ilhas do arquipélago JOI é realizada principalmente por rádio. Cada ilha possui um transmissor e um receptor de rádio. O transmissor pode emitir ondas de rádio em todas as direções, mas o receptor só consegue receber ondas vindas de uma direção específica. Assim, cada receptor só consegue receber ondas de uma determinada ilha. No entanto, mudando a orientação do receptor, é possível alterar de qual ilha ele recebe ondas.
Atualmente, o receptor da ilha $i$ ($1 \le i \le N$) consegue receber ondas da ilha $A_i$ ($A_i \ne i$). Além disso, o custo de mudar a orientação do receptor da ilha $i$ é $C_i$, independentemente da nova orientação.
O arquipélago JOI oferece um serviço público de telegramas. Quando o receptor da ilha $j$ ($1 \le j \le N$, $j \ne i$) consegue receber ondas da ilha $i$ ($1 \le i \le N$), é possível enviar um telegrama por rádio da ilha $i$ para a ilha $j$. Também é permitido enviar telegramas passando por várias ilhas. Ou seja, para ilhas $i$, $j$, $k$ ($1 \le i,j,k \le N$, com $i$, $j$, $k$ distintos entre si), se for possível enviar um telegrama da ilha $i$ para a ilha $j$ e da ilha $j$ para a ilha $k$, então é possível enviar um telegrama da ilha $i$ para a ilha $k$. Não é possível enviar telegramas por outros meios além do rádio.
Como ministro das Comunicações do arquipélago JOI, você deseja tornar possível enviar telegramas de qualquer ilha para qualquer outra. Para isso, talvez seja necessário mudar a orientação dos receptores de algumas ilhas. O custo de mudar a orientação dos receptores de várias ilhas é a soma dos custos de mudar a orientação de cada receptor.
Calcule o custo mínimo necessário para tornar possível enviar telegramas de qualquer ilha para qualquer outra.
Tarefa
Dados o número de ilhas do arquipélago JOI e as informações sobre o receptor de cada ilha, escreva um programa que determine o custo mínimo necessário para tornar possível enviar telegramas de qualquer ilha para qualquer outra.
Entrada
Leia os seguintes dados da entrada padrão.
- A primeira linha contém um inteiro $N$. Ele indica que há $N$ ilhas no arquipélago JOI.
- A $i$-ésima linha ($1 \le i \le N$) das $N$ linhas seguintes contém dois inteiros $A_i$, $C_i$, separados por um espaço. Eles indicam que o receptor da ilha $i$ consegue atualmente receber ondas da ilha $A_i$ e que o custo de mudar sua orientação é $C_i$.
Saída
Escreva, em uma linha da saída padrão, o custo mínimo necessário para tornar possível enviar telegramas de qualquer ilha para qualquer outra.
Restrições
Todos os dados de entrada satisfazem as seguintes condições.
- $2 \le N \le 100\,000$.
- $1 \le A_i \le N$ ($1 \le i \le N$).
- $A_i \ne i$ ($1 \le i \le N$).
- $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
Subtarefas
Subtarefa 1 [10 pontos]
- $N \le 10$.
Subtarefa 2 [30 pontos]
- $N \le 15$.
Subtarefa 3 [30 pontos]
- $N \le 3\,000$.
Subtarefa 4 [30 pontos]
Não há restrições adicionais.
Exemplos
Entrada 1
4 2 2 1 4 1 3 3 1
Saída 1
4
Explicação
Mude a orientação do receptor da ilha $2$ para que ele receba ondas da ilha $4$. Assim, torna-se possível enviar telegramas de qualquer ilha para qualquer outra, com custo $4$.
Nenhuma mudança de orientação dos receptores permite obter um custo inferior a $4$, portanto a saída é $4$.
Entrada 2
4 2 2 1 6 1 3 3 1
Saída 2
5
Explicação
Primeiro, mude a orientação do receptor da ilha $1$ para que ele receba ondas da ilha $4$. Depois, mude a orientação do receptor da ilha $3$ para que ele receba ondas da ilha $2$. Assim, torna-se possível enviar telegramas de qualquer ilha para qualquer outra, com custo $2+3=5$.
Nenhuma mudança de orientação dos receptores permite obter um custo inferior a $5$, portanto a saída é $5$.
Entrada 3
4 2 2 1 3 4 2 3 3
Saída 3
4
Explicação
Basta mudar a orientação dos receptores das ilhas $1$ e $3$.
Entrada 4
3 2 1 3 1 1 1
Saída 4
0
Explicação
Não é necessário mudar a orientação do receptor de nenhuma ilha.