马里奥正试图从邪恶的库巴手中救出桃花公主。但在每一关的尽头，一个叫奇诺比奥的小蘑菇人都会告诉他，公主在另一座城堡里。马里奥怀疑奇诺比奥其实是邪恶的，他只是为了好玩，不断地把马里奥送到尽可能远的城堡。

马里奥的世界可以建模为一棵包含 $N$ 个节点的树（$N$ 个节点的树是一个具有 $N-1$ 条边的连通图，节点编号从 $1$ 到 $N$），其中每个节点代表一座城堡，每条边代表一个关卡。马里奥从树的根节点开始他的旅程，并在树中穿行（可能多次经过相同的节点和边），根据奇诺比奥的指示寻找城堡里的公主。马里奥穿过一个关卡需要一定的时间（双向时间相同）。

奇诺比奥会挑选 $K$ 个不同的城堡（根节点不包含在内），马里奥必须按照给定的顺序访问它们（马里奥必须从根节点出发，并在最后回到根节点）。马里奥在从一个节点前往另一个节点时总是走最短路径。如果奇诺比奥挑选了最糟糕的 $K$ 个城堡，马里奥旅程的最大可能持续时间是多少？

输入格式

程序将测试一个或多个测试用例。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$ ($2 \le N \le 1,000$) ($1 \le K \le 100$) ($1 \le K \le N - 1$)，分别表示树中城堡的总数和马里奥必须访问的城堡数量。随后有 $N-1$ 行，每行描述节点 $2$ 到 $N$。每行包含两个整数 $P_i$ 和 $C_i$ ($1 \le P_i \le N$) ($0 \le C_i \le 100,000$)，分别表示第 $i$ 个节点的父节点（此处 $i$ 从 $2$ 开始）以及通过连接当前节点与其父节点的边所需的时间。节点 $1$ 是树的根节点。

输出格式

对于每个测试用例，打印一行包含 “Case n:”（不含引号），其中 $n$ 是测试用例编号（从 $1$ 开始），后跟一个空格，再后跟马里奥旅程的最大持续时间。

样例

输入 1

3
3 1
1 5
1 3
4 2
1 5
1 3
3 2
5 3
1 5
1 3
3 2
3 10

输出 1

Case 1: 10
Case 2: 20
Case 3: 46

说明

对于第三个测试用例，奇诺比奥可能给出的列表之一是：5, 2, 4。