Educational Codeforces Round 49 (Rated for Div. 2)-D-Mouse Hunt（贪心）

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 nn 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 ii costs cici burles. Rooms are numbered from 11 to nn.

Mouse doesn't sit in place all the time, it constantly runs. If it is in room ii in second tt then it will run to room aiai in second t+1t+1 without visiting any other rooms inbetween (i=aii=ai means that mouse won't leave room ii). 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 nn 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 nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of rooms in the dormitory.

The second line contains nn integers c1,c2,…,cnc1,c2,…,cn (1≤ci≤1041≤ci≤104) — cici is the cost of setting the trap in room number ii.

The third line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n) — aiai is the room the mouse will run to the next second after being in room ii.

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

5
1 2 3 2 10
1 3 4 3 3

output

Copy

3

input

Copy

4
1 10 2 10
2 4 2 2

output

Copy

10

input

Copy

7
1 1 1 1 1 1 1
2 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:

• 1→2→2→…1→2→2→…;
• 2→2→…2→2→…;
• 3→2→2→…3→2→2→…;
• 4→3→2→2→…4→3→2→2→…;
• 5→6→7→6→…5→6→7→6→…;
• 6→7→6→…6→7→6→…;
• 7→6→7→…7→6→7→…;

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

题意：给你若干个房间，还有一只老鼠穿梭其中，老鼠的起始位置是随意的，假如老鼠在第i个房间，则它下次的目的地是ai，然后你可以在若干个房间里设置老鼠夹来捕捉老鼠，每个房间放置老鼠夹的代价是bi，你可以在任意房间放老鼠夹，但是你必须要使得不管老鼠从哪里出发都能捉到老鼠，问你花费的总代价是多少？

题解：很容易想到的是，若一些房间构成了一个环，则只用在这个环中找一个房间放置老鼠夹就行了，因此我们可以对于每个环找出花费代价最小的房间设置老鼠夹。当然有些还上会存在一些链，因此我们可以用标记数组巧妙地标记不属于环内的房间即可，这些房间一定不用放置老鼠夹的，具体见代码。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
#define maxn 200005
int n,a[maxn],b[maxn],ans,flag[maxn];
int main(void)
{
	int cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
	{
		if(flag[i]) continue;
		int p=i; cnt++;
		while(1)
		{
			flag[p]=cnt;p=b[p];
			if(flag[p]==cnt)
			{
				int des=p;
				int t=b[des];
				int tmp=a[des];
				while(t!=des)
					tmp=min(tmp,a[t]),t=b[t];
				ans+=tmp;
				break;
			}
			else if(flag[p] && flag[p]!=cnt)
				break;
		}
	}
	printf("%d\n",ans);
	return 0;
}