Codeforces 1027D Mouse Hunt

Medicine faculty of Berland State University has just finished their admission campaign. As usual, about 80% of applicants are girls and majority of them are going to live in the university dormitory for the next 4 (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 1 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 without visiting any other rooms inbetween (i=ai means that mouse won't leave room i). It's second 0 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 1 to n at second 0.

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(1≤n≤2⋅10^5) — the number of rooms in the dormitory.

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

The third line contains n integers a1,a2,…,an (1≤ai≤n) — 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

5
1 2 3 2 10
1 3 4 3 3

Output

3

Input

4
1 10 2 10
2 4 2 2

Output

10

Input

7
1 1 1 1 1 1 1
2 2 2 3 6 7 6

Output

2

Note

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

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

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

 

题意：有一只老鼠在n个房间串，每一秒过后就会去下一个房间，而且这个去的房间你是知道的。在每一个房间布置老鼠夹得费用也告诉你，然后让你求不管老鼠一开始在哪个房间，你都能抓住老鼠的最小费用是多少？

 

解题过程：首先我们知道自环的就一定是需要你加上自环的房间的费用。然后剩下的就是一定到达某一个环停止。为什么呢？题目说老鼠每一秒后都会去下一个房间，假设老鼠在一条链上，那么当他到终点的时候他一定会到上面之前经过的某一个点。也就是说一定存在环的结构。那么我们就只需要拓扑一下就行。把入度为0的点先删去，最后剩下环的时候我们再分别求每一个环的最小值，累加就行。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
int n,m,de[maxn],c[maxn],a[maxn];
bool vis[maxn];
void init(){
	mem(vis,0);mem(de,0);
}
queue<int> qu;
int main(){
	int i,j;
	while(scanf("%d",&n)!=EOF){
		init();
		ll ans=0;
		int u,v;
		for(i=1;i<=n;i++){
			scanf("%d",&c[i]);
		}
		for(i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(a[i]==i){
				ans+=c[i];
				vis[i]=1;
			}
			else{
				de[a[i]]++;
			}
		}
		int sum=0;
		while(!qu.empty()) qu.pop();
		for(i=1;i<=n;i++){
			if(!vis[i]&&de[i]==0) qu.push(i),sum++,vis[i]=1;
		}
		while(!qu.empty()){
			int u=qu.front();qu.pop();
			de[a[u]]--;
			if(!de[a[u]]&&!vis[a[u]]){
				vis[a[u]]=1;
				sum++;
				qu.push(a[u]);
			}
		}
		
		for(i=1;i<=n;i++){
			if(!vis[i]){
				vis[i]=1;
				int k=c[i],u=a[i];
				while(u!=i){
					vis[u]=1;
					k=min(k,c[u]);
					u=a[u];
				}
				ans+=k;
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}
//10
//6 9 1 1 1 10 2 4 9 6
//5 3 4 2 6 8 9 1 10 7