题目描述

Alice 和 Bob 正在玩一款星际开发游戏。游戏中有 $n$ 个星球，编号为 $1$ 到 $n$。星球 $u$ 上的矿物储量为 $w_u$。

为了在不同星球之间移动，星际公司建造了 $n-1$ 个星门，规则如下：

• 对每个星球 $u\in\{2,3,\dots,n\}$，星球 $u$ 上恰好有一个星门；
• 给定 $p_2,p_3,\dots,p_n$，星球 $u$ 上的星门通向星球 $p_u$；
• 星门是单向的，不能反向通过；
• 从任意星球出发，都可以沿星门到达星球 $1$。星球 $1$ 上有星际市场。

Bob 有 $k$ 艘采矿船。他可以把这 $k$ 艘采矿船部署到 $k$ 个不同的星球上。每艘采矿船可以沿星门移动，并收集其路径上经过星球的全部矿物储量。一个星球可以被多艘采矿船经过，但每个星球上的矿物最多只能被收集一次。最终，采矿船会到达星球 $1$，并在那里出售收集到的矿物。

然而，在 Bob 开始采矿前，触发了一次星门维护事件。星际公司决定更新星门布局：拆除 $t$ 个星门，并重新建造 $t$ 个星门，使得更新后的星门结构仍满足上述规则。由于游戏机制，$t$ 可以是 $[0,n-1]$ 内的任意整数，也就是说，星门可以完全不更新。

经过一番外交点数交易后，拆除星门的任务被外包给 Alice，重建星门的任务被外包给 Bob。重建完成后，Bob 再部署采矿船进行采矿。

Bob 希望最大化自己收集到的矿物总量；Alice 希望最小化 Bob 最终能收集到的矿物总量。在此基础上，Alice 还希望拆除尽可能多的星门。

假设双方都采取最优策略，求：

1. Bob 最终能收集到的矿物总量；
2. 在保证该矿物总量最小的前提下，Alice 最多能拆除多少个星门。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含两个正整数 $n,k$。

第二行包含 $n$ 个正整数 $w_1,w_2,\dots,w_n$，表示每个星球上的矿物储量。

第三行包含 $n-1$ 个正整数 $p_2,p_3,\dots,p_n$，表示初始状态下星球 $u$ 上的星门通向星球 $p_u$。

输出格式

对于每组测试数据，输出一行两个非负整数，分别表示：

• Bob 最终收集到的矿物总量；
• 在使 Bob 收集总量最小的前提下，Alice 最多能拆除的星门数量。

样例

样例输入

3
3 1
1 1 1
1 1
7 2
5 8 8 5 8 2 3
1 2 3 4 1 4
16 4
2 7 9 7 9 5 10 10 2 10 5 2 7 6 9 4
1 1 3 3 1 6 5 8 3 10 2 7 8 9 3

样例输出

2 0
37 2
87 4

样例解释

对于第一组测试数据，如果 Alice 拆除星球 $2$ 上的星门，那么 Bob 可以将其重建为 $p_2=3$，于是他只需要把唯一一艘采矿船放在星球 $2$，就能收集三个星球上的全部 $3$ 单位矿物。拆除星球 $3$ 上的星门时情况类似。

因此，Alice 最优选择是不拆除任何星门，此时 Bob 最多只能收集到 $2$ 单位矿物。

对于第二组测试数据，Alice 的一种可行最优策略是拆除星球 $2$ 和星球 $3$ 上的星门。

数据范围

令 $\sum n$ 表示单个测试文件中所有测试数据的 $n$ 之和。保证：

• $1\le T\le 10^4$；
• $1\le k\le n\le 2\times 10^5$；
• $1\le \sum n\le 5\times 10^5$；
• $1\le w_u\le 10^9$；
• 对所有 $2\le u\le n$，有 $1\le p_u\le u-1$。

子任务

特殊性质：

• A：$k=1$；
• B：对所有 $2\le u\le n$，都有 $p_u=1$ 或 $p_u=u-1$。