유치원 사탕 나누기

면접 대비

시간 제한2초메모리 제한256 MB

요약

아이마다 정확히 한 명을 지목하고 지목 대상이 겹치지 않아 순열을 이룰 때, 각 아이가 받은 사탕과 자신이 지목한 아이가 받은 사탕의 차의 최댓값을 최소로 만드는 배정을 찾는다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 그리디, 배열, 정렬
정답자: 아직 제출이 없습니다

문제

유치원에 아이가 $N$ 명 있고, 아이마다 가장 친한 친구를 한 명씩 정해 두었다. 서로 다른 두 아이가 같은 아이를 가장 친한 친구로 꼽는 일은 없다. 자기 자신을 가장 친한 친구로 꼽는 아이는 있을 수 있고, $A$ 가 꼽은 친구가 $B$ 라고 해서 $B$ 가 $A$ 를 꼽는 것은 아니다.

선생님은 사탕 봉지 $N$ 개를 아이 한 명당 한 봉지씩 나눠 준다. 봉지마다 든 사탕 개수가 달라서 아이들이 불만을 품는다. 아이들은 공평함에 민감해서, 아이 $A$ 의 불만도는 $A$ 가 받은 사탕 개수와 $A$ 가 꼽은 친구가 받은 사탕 개수의 차이의 절댓값이다.

선생님은 아이들의 불만도 중 최댓값이 가장 작아지도록 봉지를 나눠 주려고 한다. 최대 불만도의 최솟값을 구하라.

입력

첫째 줄에 아이의 수 $N$ 이 주어진다. ( $1 \le N \le 150$ )

둘째 줄에 서로 다른 정수 $N$ 개가 주어진다. $i$ 번째 수는 $i$ 번 아이가 가장 친한 친구로 꼽은 아이의 번호다. 아이의 번호는 $1$ 번부터 $N$ 번까지다.

셋째 줄에 정수 $N$ 개가 주어진다. $i$ 번째 수는 $i$ 번 봉지에 든 사탕 개수이고, $0$ 이상 $10^9$ 이하다.

출력

최대 불만도의 최솟값을 한 줄에 출력한다.

예제3

예제 1
입력
```
3
2 1 3
3 8 5
```
예상 출력
```
2
```
예제 2
입력
```
5
3 5 4 1 2
24 45 39 19 16
```
예상 출력
```
8
```
예제 3
입력
```
8
6 3 7 1 4 8 2 5
6 5 2 4 7 4 4 3
```
예상 출력
```
2
```