마리오와 사악한 키노피오

마리오는 사악한 쿠파에게 붙잡힌 피치 공주를 구하려고 성을 누비고 다닌다. 그런데 어떤 스테이지를 깨도 작은 버섯 인간(키노피오)은 공주가 다른 성에 있다는 말만 한다. 마리오는 이 키노피오가 아주 사악해서 그저 재미로 자신을 가장 먼 성까지 보내려 한다고 의심한다.

마리오의 세계는 노드가 $N$개인 트리다. 간선은 $N-1$개이고 그래프는 연결되어 있으며, 노드에는 $1$번부터 $N$번까지 번호가 붙어 있다. 노드마다 성이 하나씩 있고, 간선 하나는 스테이지 하나를 뜻한다. 스테이지 하나를 지나는 데 걸리는 시간은 간선마다 정해져 있고, 양쪽 방향에서 같다.

키노피오는 서로 다른 성 $K$개를 고른다. 루트인 $1$번 성은 고르지 않는다. 마리오는 고른 성을 반드시 주어진 순서대로 방문해야 한다. 여행은 $1$번 성에서 시작해 $1$번 성에서 끝낸다. 성에서 성으로 움직일 때는 항상 최단 경로로만 이동하며, 같은 노드나 간선을 여러 번 지날 수 있다.

키노피오가 성 $K$개와 그 순서를 마음대로 정할 때, 마리오가 여행에 쓰는 시간의 최댓값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫째 줄에 정수 $N$과 $K$가 주어진다. ($2 \le N \le 1000$, $1 \le K \le 100$, $1 \le K \le N-1$) $N$은 성의 개수, $K$는 키노피오가 고르는 성의 개수다.

다음 $N-1$개 줄에 $2$번 노드부터 $N$번 노드까지의 정보가 차례대로 주어진다. 각 줄에는 정수 $P_i$와 $C_i$가 주어지며 ($1 \le P_i \le N$, $0 \le C_i \le 100000$), $P_i$는 그 노드의 부모 노드 번호, $C_i$는 그 노드와 부모 사이의 스테이지를 지나는 데 걸리는 시간이다.

루트는 항상 $1$번 노드이고, 주어진 $N-1$개의 간선은 언제나 $1$번을 루트로 하는 트리를 이룬다. 부모 노드의 번호가 자식 노드의 번호보다 클 수도 있다.

각 테스트 케이스마다 한 줄에 Case n: 형식에 이어 답을 출력한다. $n$은 테스트 케이스의 번호이며 $1$부터 시작한다.

예제의 세 번째 테스트 케이스에서는 키노피오가 $5$, $2$, $4$번 성을 이 순서로 고르면 최댓값이 나온다. $4$, $2$, $5$번 순서도 같은 값을 준다.