D. Охота за мышью
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Медицинский факультет Берляндского Государственного Университета недавно завершил свою приемную кампанию. Как обычно, порядка $$$80\%$$$ абитуриентов — девушки, и большинство из них планируют жить в общежитии в ближайшие $$$4$$$ (в лучшем случае) года.

Общежитие состоит из $$$n$$$ комнат и единственной мыши! Девушки решили установить ловушки для мышей в некоторых комнатах, чтобы избавиться от страшного монстра. Установка ловушки в $$$i$$$-й комнате стоит $$$c_i$$$ бурлей. Комнаты пронумерованы от $$$1$$$ до $$$n$$$.

Мышь не сидит все время на месте, она постоянно бегает. Если она находилась в комнате $$$i$$$ в секунду $$$t$$$, то к секунде $$$t + 1$$$ она перебежит в комнату $$$a_i$$$, не посещая больше никаких других комнат ($$$i = a_i$$$ значит, что мышь не покинет комнату $$$i$$$). История начинается с секунды $$$0$$$. Если мышь находится в комнате с ловушкой, то она оказывается поймана в эту ловушку.

И все было бы довольно просто, если бы девушки знали, где мышь находится. К сожалению, это не так, мышь может быть в любой комнате от $$$1$$$ до $$$n$$$ в секунду $$$0$$$.

Какое минимальное количество бурлей девушки должны потратить на установку ловушек, чтобы гарантировать, что мышь будет поймана вне зависимости от комнаты, в которой она начинала.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество комнат в общежитии.

Во второй строке записаны $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^4$$$) — $$$c_i$$$ — стоимость установки ловушки в комнату $$$i$$$.

В третьей строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — $$$a_i$$$ — комната, в которую перебежит мышь к следующей секунде, из комнаты $$$i$$$.

Выходные данные

Выведите единственное целое число — минимальное количество бурлей, которое девушки должны потратить на установку ловушек, чтобы гарантировать, что мышь будет поймана вне зависимости от комнаты, в которой она начинала.

Примеры
Входные данные
5
1 2 3 2 10
1 3 4 3 3
Выходные данные
3
Входные данные
4
1 10 2 10
2 4 2 2
Выходные данные
10
Входные данные
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
Выходные данные
2
Примечание

В первом примере достаточно установить ловушку в комнаты $$$1$$$ и $$$4$$$. Если мышь начнет в комнате $$$1$$$, то будет поймана сразу. Если мышь начнет в любой другой комнате, то она прибежит в комнату $$$4$$$ рано или поздно.

Во втором примере достаточно установить ловушку в комнату $$$2$$$. Если мышь начнет в комнате $$$2$$$, то будет поймана сразу. Если мышь начнет в любой другой комнате, то она прибежит в комнату $$$2$$$ в секунду $$$1$$$.

Пути мыши, начиная с каждой комнаты, для третьего примера:

  • $$$1 \rightarrow 2 \rightarrow 2 \rightarrow \dots$$$;
  • $$$2 \rightarrow 2 \rightarrow \dots$$$;
  • $$$3 \rightarrow 2 \rightarrow 2 \rightarrow \dots$$$;
  • $$$4 \rightarrow 3 \rightarrow 2 \rightarrow 2 \rightarrow \dots$$$;
  • $$$5 \rightarrow 6 \rightarrow 7 \rightarrow 6 \rightarrow \dots$$$;
  • $$$6 \rightarrow 7 \rightarrow 6 \rightarrow \dots$$$;
  • $$$7 \rightarrow 6 \rightarrow 7 \rightarrow \dots$$$;

Поэтому достаточно установить ловушки в комнатах $$$2$$$ и $$$6$$$.