У Беси есть \(N\) (\(2\le N\le 10^5\)) приятелей - быков, последовательно пронумерованных \(1\ldots N\).
Для каждого \(1\le i\le N\), бык \(i\) хочет посетить быка \(a_i\) (\(a_i\neq i\)).
Задана перестановка \((p_1,p_2,\ldots, p_N)\) из \(1\ldots N\), указывающая
как произошли посещения.
Для каждого \(i\) от \(1\) до \(N\):
- Если бык \(a_{p_i}\) уже ушёл со своей фермы, то бык \(p_i\) остаётся на своей ферме.
- Иначе бык \(p_i\) уходит со своей фермы на ферму \(a_{p_i}\). Этот визит завершается
радостным "moo" произнесённым \(v_{p_i}\) раз (\(0\le v_{p_i}\le 10^9\)).
Вычислите максимально возможное количество "moo" после всех визитов по всем возможным
перестановкам \(p\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит число
\(N\).
Для каждого \(1\le i\le N\), \(i+1\)-ая строка содержит два разделённых пробелом
целых числа \(a_i\) и \(v_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Одно целое число - ответ.
Заметим, что при вычислениях может потребоваться использование
64-битного типа целых чисел (например, long long в C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 10
3 20
4 30
1 40
|
90
|