Медицинский факультет Берляндского Государственного Университета недавно завершил свою приемную кампанию. Как обычно, порядка \(80\%\) абитуриентов — девушки, и большинство из них планируют жить в общежитии в ближайшие \(4\) (в лучшем случае) года.
Общежитие состоит из \(n\) комнат и единственной мыши! Девушки решили установить ловушки для мышей в некоторых комнатах, чтобы избавиться от страшного монстра. Установка ловушки в \(i\)-й комнате стоит \(c_i\) бурлей. Комнаты пронумерованы от \(1\) до \(n\).
Мышь не сидит все время на месте, она постоянно бегает. Если она находилась в комнате \(i\) в секунду \(t\), то к секунде \(t + 1\) она перебежит в комнату \(a_i\), не посещая больше никаких других комнат (\(i = a_i\) значит, что мышь не покинет комнату \(i\)). История начинается с секунды \(0\). Если мышь находится в комнате с ловушкой, то она оказывается поймана в эту ловушку.
И все было бы довольно просто, если бы девушки знали, где мышь находится. К сожалению, это не так, мышь может быть в любой комнате от \(1\) до \(n\) в секунду \(0\).
Какое минимальное количество бурлей девушки должны потратить на установку ловушек, чтобы гарантировать, что мышь будет поймана вне зависимости от комнаты, в которой она начинала.
Выходные данные
Выведите единственное целое число — минимальное количество бурлей, которое девушки должны потратить на установку ловушек, чтобы гарантировать, что мышь будет поймана вне зависимости от комнаты, в которой она начинала.
Примечание
В первом примере достаточно установить ловушку в комнаты \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 2 10
1 3 4 3 3
|
3
|
|
2
|
4
1 10 2 10
2 4 2 2
|
10
|
|
3
|
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
|
2
|