## Algorithm

D. Mouse Hunt
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Medicine faculty of Berland State University has just finished their admission campaign. As usual, about 80%80% of applicants are girls and majority of them are going to live in the university dormitory for the next 44 (hopefully) years.

The dormitory consists of n rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number i costs ci�� burles. Rooms are numbered from 11 to n.

Mouse doesn't sit in place all the time, it constantly runs. If it is in room i in second t then it will run to room ai�� in second t+1�+1 without visiting any other rooms inbetween (i=ai�=�� means that mouse won't leave room i). It's second 00 in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.

That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that's not the case, mouse can be in any room from 11 to n at second 00.

What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?

Input

The first line contains as single integers n (1n21051≤�≤2⋅105) — the number of rooms in the dormitory.

The second line contains n integers c1,c2,,cn�1,�2,…,�� (1ci1041≤��≤104) — ci�� is the cost of setting the trap in room number i.

The third line contains n integers a1,a2,,an�1,�2,…,�� (1ain1≤��≤�) — ai�� is the room the mouse will run to the next second after being in room i.

Output

Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.

Examples
input
Copy
51 2 3 2 101 3 4 3 3
output
Copy
3
input
Copy
41 10 2 102 4 2 2
output
Copy
10
input
Copy
71 1 1 1 1 1 12 2 2 3 6 7 6
output
Copy
2
Note

In the first example it is enough to set mouse trap in rooms 11 and 44. If mouse starts in room 11 then it gets caught immideately. If mouse starts in any other room then it eventually comes to room 44.

In the second example it is enough to set mouse trap in room 22. If mouse starts in room 22 then it gets caught immideately. If mouse starts in any other room then it runs to room 22 in second 11.

Here are the paths of the mouse from different starts from the third example:

• 1221→2→2→…;
• 222→2→…;
• 3223→2→2→…;
• 43224→3→2→2→…;
• 56765→6→7→6→…;
• 6766→7→6→…;
• 7677→6→7→…;

So it's enough to set traps in rooms 22 and 66.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, c[N], comp[N], id, dfs, idx[N], low[N];
bool in[N], vis[N];
vector<int> st;
vector<vector<int> > g, ng, comps;

void DFS(int v) {
idx[v] = low[v] = dfs++;
in[v] = true;
st.push_back(v);

for(int i = 0, u; i < g[v].size(); ++i) {
u = g[v][i];
if(idx[u] == -1) {
DFS(u);
low[v] = min(low[v], low[u]);
} else if(in[u])
low[v] = min(low[v], low[u]);
}

if(low[v] == idx[v]) {
int node;
do {
node = st.back();
comps[id].push_back(node);
comp[node] = id;
in[node] = false;
st.pop_back();
} while(node != v);
++id;
}
}

int main() {
scanf("%d", &n);
g.resize(n);
comps.resize(n);
for(int i = 0; i < n; ++i)
scanf("%d", c + i);
for(int i = 0, tmp; i < n; ++i) {
scanf("%d", &tmp), --tmp;
g[i].push_back(tmp);
}

memset(idx, -1, sizeof idx);
dfs = id = 0;
for(int i = 0; i < n; ++i)
if(idx[i] == -1)
DFS(i);

ng.resize(n);
for(int i = 0; i < g.size(); ++i)
for(int j = 0; j < g[i].size(); ++j)
if(comp[i] != comp[g[i][j]])
ng[comp[i]].push_back(comp[g[i][j]]);

int res = 0;
for(int i = 0; i < id; ++i)
if(ng[i].size() == 0) {
int mn = 1e9;
for(int j = 0; j < comps[i].size(); ++j)
mn = min(mn, c[comps[i][j]]);
res += mn;
}

printf("%d\n", res);

return 0;
}
Copy The Code &

Input

cmd
5
1 2 3 2 10
1 3 4 3 3

Output

cmd
3