연쇄 반응

Wile은 사막에서 혼자 살기 때문에 연쇄 반응으로 작동하는 복잡한 기계를 만들며 즐긴다. 각 기계는 $1, 2, \dots, \mathbf{N}$로 번호가 매겨진 $\mathbf{N}$개의 모듈로 구성된다. 각 모듈은 인덱스가 더 작은 다른 모듈 하나를 가리킬 수 있다. 그렇지 않으면 심연을 가리킨다.

다른 어떤 모듈도 가리키지 않는 모듈을 개시자라고 한다. Wile은 개시자를 수동으로 작동시킬 수 있다. 모듈이 작동하면 자신이 가리키는 모듈이 있다면 그 모듈을 작동시키고, 그 모듈도 다른 모듈을 가리킨다면 세 번째 모듈을 작동시킬 수 있으며, 이런 과정은 연쇄가 심연에 도달하거나 이미 작동한 모듈에 도달하려 할 때까지 계속된다. 이를 연쇄 반응이라고 한다.

$\mathbf{N}$개의 각 모듈에는 재미 지수 $\mathbf{F_i}$가 있다. Wile이 한 번의 연쇄 반응에서 얻는 재미는 그 연쇄 반응에서 작동한 모든 모듈의 재미 지수 중 가장 큰 값이다. Wile은 각 개시자 모듈을 어떤 순서로든 한 번씩 작동시킬 것이다. Wile이 이 시간 동안 얻는 전체 재미는 각 연쇄 반응에서 얻는 재미의 합이다.

예를 들어 Wile에게 재미 지수가 $\mathbf{F_1}=60, \mathbf{F_2}=20, \mathbf{F_3}=40,$와 $\mathbf{F_4}=50$인 $4$개의 모듈이 있고, 모듈 $1$은 심연을, 모듈 $2$과 $3$는 모듈 $1$을, 모듈 $4$은 모듈 $2$를 가리킨다고 하자. Wile이 어떤 순서로든 작동시켜야 하는 개시자는 두 개($3$과 $4$)이다.

위에서 볼 수 있듯이 Wile이 모듈 $4$을 먼저 수동으로 작동시키면, 모듈 $4$, $2$, $1$이 같은 연쇄 반응에서 작동하여 재미는 $\max(50, 20, 60) = 60$가 된다. 그다음 Wile이 모듈 $3$을 작동시키면 모듈 $3$만 작동하고(모듈 $1$은 다시 작동할 수 없다), 재미는 $40$가 되며, 이 시간 동안의 전체 재미는 $60+40=100$가 된다.

하지만 Wile이 모듈 $3$을 먼저 수동으로 작동시키면, 모듈 $3$과 $1$이 같은 연쇄 반응에서 작동하여 재미는 $\max(40, 60) = 60$가 된다. 그다음 Wile이 모듈 $4$을 작동시키면 모듈 $4$과 $2$이 같은 연쇄 반응에서 작동하여 재미는 $\max(50, 20) = 50$가 되며, 이 시간 동안의 전체 재미는 $60+50=110$가 된다.

재미 지수와 모듈의 구성이 주어질 때, Wile이 개시자들을 가능한 최선의 순서로 작동시켜 얻을 수 있는 최대 재미를 계산한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{F_i} \le 10^9$. 모든 $i$에 대해 $0 \le \mathbf{P_i} \le i - 1$.

테스트 세트 1 (Visible Verdict)

시간 제한: 5초. $1 \le \mathbf{N} \le 10$.

테스트 세트 2 (Visible Verdict)

시간 제한: 5초. $1 \le \mathbf{N} \le 1000$.

테스트 세트 3 (Hidden Verdict)

시간 제한: 10초. $1 \le \mathbf{N} \le 100000$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 각각 3개의 줄로 설명되는 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Wile이 가진 모듈의 수를 나타내는 정수 하나 $\mathbf{N}$가 있는 줄로 시작한다. 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{F_1}, \mathbf{F_2}, \dots, \mathbf{F_N}$가 주어지며, $\mathbf{F_i}$는 $i$번째 모듈의 재미 지수이다. 세 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{P_1}, \mathbf{P_2}, \dots \mathbf{P_N}$가 주어진다. $\mathbf{P_i}=0$이면 모듈 $i$이 심연을 가리킨다는 뜻이다. 그렇지 않으면 모듈 $i$가 모듈 $\mathbf{P_i}$를 가리킨다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 (1부터 시작), $y$는 Wile이 개시자들을 가능한 최선의 순서로 수동 작동시켜 얻을 수 있는 최대 재미이다.

예제 케이스 #1은 문제 설명에서 설명한 케이스이다.

예제 케이스 #2에는 $4$개의 개시자(모듈 $2$부터 $5$까지)가 있으므로, $4$개의 연쇄 반응이 있다. 이들을 $3, 5, 4, 2$ 순서로 작동시키면 재미가 $3, 5, 4, 2$인 연쇄들이 만들어지고, 전체 재미는 $14$가 된다. 입력에서 가장 높은 네 개의 재미 수치를 더한 값이므로, 이보다 더 큰 값을 얻을 방법은 없다는 점에 유의한다.

예제 케이스 #3에서 $5$개의 개시자를 작동시키는 최적의 순서는 $4, 5, 7, 6, 8$이다.