철도 운영

당신은 철도망의 운영을 담당한다. 이 철도망은 $\mathbf{N}$개의 역으로 이루어진다. 각 역 $i$은 정확히 하나의 다른 역 $\mathbf{D_i}$으로 화물을 보내야 한다. 역 $i$은 정확히 $\mathbf{C_i}$개의 철도 차량으로 이루어진 열차를 이용해 화물을 정확히 한 번 보낸다.

모든 화물 운송 정보를 훨씬 미리 알 수 있으므로, 철도 차량을 재사용하여 필요한 차량 수를 줄이려 한다. 역 $i$이 역 $\mathbf{D_i}$으로 $n$개의 철도 차량을 보내면, $\mathbf{D_i}$은 자신의 화물 운송이 아직 이루어지지 않은 경우 그 철도 차량을 자신의 보유 차량에 추가하여 자신의 화물 운송에 사용할 수 있다.

형식적으로, 각 역에 초기 철도 차량을 지급해야 하며(일부 역은 $0$을 받을 수도 있다), 화물 운송 순서를 정해야 한다. 역 $i$이 화물을 보내야 할 때까지, 그 역의 초기 보유 차량과 이전에 $i$에 도착한 모든 화물 운송으로 받은 철도 차량을 합친 수가 자체 화물 운송에 필요한 차량 수 $\mathbf{C_i}$ 이상이어야 한다. 역에 $\mathbf{C_i}$개보다 많은 차량이 있더라도, 역 $i$에서 출발하는 한 번의 화물 운송으로 $\mathbf{C_i}$개보다 많은 차량을 보낼 수는 없다.

예를 들어, 역 $1$이 정확히 $3$개의 철도 차량을 실은 열차를 역 $4$으로 보낸다고 하자. 이제 역 $4$에 $2$개의 차량이 필요하다면, 역 $1$에서 받은 차량 중 $2$개를 재사용할 수 있다. 또한 역 $4$이 $5$개의 차량을 보내야 한다면, 역 $1$에서 받은 $3$개의 차량을 모두 재사용하고 자체 보유 차량 중 $2$개를 추가할 수 있다. 역 $4$이 $2$개의 차량을 보내야 할 때는 역 $1$에서 받은 $3$개를 모두 보낼 수 없다는 점에 유의하라.

화물 운송 정보가 주어질 때, 어떤 순서로든 모든 화물 운송을 수행할 수 있도록 각 역의 초기 보유 차량으로 지급해야 하는 철도 차량 수의 최솟값은 얼마인가?

제한

시간 제한: 40초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{D_i} \le \mathbf{N}$. 모든 $i$에 대해 $\mathbf{D_i} \ne i$. 모든 $i$에 대해 $1 \le \mathbf{C_i} \le 10^9$.

테스트 세트 1 (Visible Verdict)

$2 \le \mathbf{N} \le 8$.

테스트 세트 2 (Visible Verdict)

$2 \le \mathbf{N} \le 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 $3$줄로 이루어진다. 첫 줄에는 철도망의 역 수를 나타내는 정수 하나 $\mathbf{N}$이 주어진다. 둘째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{D_1}, \mathbf{D_2}, \dots, \mathbf{D_N}$가 주어지고, 셋째이자 마지막 줄에는 $\mathbf{N}$개의 정수 $\mathbf{C_1}, \mathbf{C_2}, \dots, \mathbf{C_N}$가 주어진다. 이는 역 $i$이 정확히 $\mathbf{C_i}$개의 철도 차량으로 이루어진 열차를 역 $\mathbf{D_i}$으로 보내야 함을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 화물 운송을 수행할 수 있도록 역들에 지급해야 하는 철도 차량 수의 최솟값이다.

예제 케이스 #1에서 한 가지 최적의 방법은 출발역의 오름차순으로 화물 운송을 수행하는 것이다. 그러려면 역 $1$에 $4$개의 차량을 보내야 한다. 하지만 그 이후에는 각 역이 자체 화물 운송에 충분한 차량을 받으므로, 전체 합계는 $4$가 된다. 역 $1$에는 어떤 차량도 도착하지 않으므로 초기 차량 $4$이 반드시 필요하며, 따라서 이 값은 가능한 최솟값이기도 하다.

예제 케이스 #2에서 한 가지 최소 지급 방법은 역 $3$에 $1$개의 차량을, 역 $2$과 $4$에 각각 $2$개의 차량을 지급하여 합계 $5$개로 만드는 것이다. 그런 다음 화물 운송 $3 \to 4$부터 시작할 수 있으며, 이를 통해 역 $4$은 차량을 하나 더 받는다. 그 결과 역 $4$에는 화물 운송 $4 \to 1$에 필요한 $3$개의 차량이 있게 된다. 이제 역 $1$에는 $3$개의 차량이 있으며, 이는 차량 하나로 $1 \to 2$을 수행하기에 충분하다. 그러면 역 $2$의 차량 수는 총 $3$개가 되어 마지막 화물 운송 $2 \to 3$을 수행하기에 충분해진다. 사용할 수 있는 차량이 있고 그렇게 하는 것이 도움이 되더라도, 화물 운송 $1 \to 2$은 역 $2$에 추가 차량을 가져다줄 수 없다는 점에 유의하라. 초기 차량 $5$개로 모든 화물 운송을 수행하는 다른 방법들도 있지만, 그보다 적은 차량으로 수행할 방법은 없다.

예제 케이스 #3에서 한 가지 최적의 초기 차량 배치는 역 $1$과 $4$에 각각 $3$개, 역 $5$과 $7$에 각각 $2$개의 차량을 두는 것이다.