31030번 - 순열과 수열

문제

길이 $N$의 순열은 1,ドル 2, \cdots , N$이 정확히 한 번 등장하는 수열이다. 예를 들어, $[2, 3, 1, 4]$나 $[6, 4, 5, 1, 2, 3]$은 모두 순열이지만 $[1, 2, 2]$나 $[1, 2, 3, 5]$는 순열이 아니다. 길이 $N$의 순열 $A$와 길이 $N$의 수열 $X$가 주어진다.

다음 조건에 맞는 길이 $N$의 수열 $B$ 중에서 $X_1 B_1 + X_2 B_2 + \cdots + X_N B_N$의 최댓값을 출력하라.

• $B$의 각 원소는 1ドル$ 이상, $N$ 이하의 정수이다.
• 1ドル \le i \le N$인 모든 양의 정수 $i$에 대하여 $A_{B_i}=B_{A_i}$

모든 순열 $A$에 대해 위 조건을 만족하는 수열 $B$가 하나 이상 존재한다는 것을 증명할 수 있다.

입력

첫째 줄에 정수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots A_N$이 공백을 사이에 두고 주어진다.

셋째 줄에 $N$개의 정수 $X_1, X_2, \cdots X_N$이 공백을 사이에 두고 주어진다.

출력

첫째 줄에 조건에 맞는 수열 $B$ 중에서 $X_1 B_1 + X_2 B_2 + \cdots X_N B_N$의 최댓값을 출력하라.

제한

• 1ドル \leq N \leq 5,000円$
• $A$는 길이 $N$의 순열이다.
• 1ドル \le X_i \le 1,000円,000円,000円$
• 주어지는 모든 수는 정수이다.

힌트