Little Q 有一棵包含 $n$ 个节点的苹果树，节点编号为 $1, 2, \dots, n$。树的根节点为 $1$，每条边的长度为 $1$ 个单位。第 $i$ 个节点上有 $a_i$ 个苹果。每个苹果的价格为 $1$ 美元，因此如果你卖出 $t$ 个苹果，你将获得 $t$ 美元。

Little Q 的好友 Skywalkert 在编程竞赛中赌博输光了大部分钱，所以他想从这棵苹果树上偷一些苹果并卖掉赚钱。

安保系统使用 $m$ 个摄像头每小时对节点进行一次拍照。令 $d(x, y)$ 表示从节点 $x$ 到节点 $y$ 的最短路径上的边数，并令集合 $p(x, k)$ 为 $\{y \mid y \text{ 在 } x \text{ 的子树中且 } d(x, y) \le k\}$。注意 $x \in p(x, k)$。第 $i$ 个摄像头的图像显示了 $p(x_i, k_i)$ 中所有节点的画面。如果安保系统检测到这些图像中的任何一个发生了变化，它就会拉响警报，小偷就会被 Little Q 抓住。

Skywalkert 也是一名天才黑客。他可以锁定一些摄像头，使得这些摄像头的图像永远不会改变。具体来说，如果他想锁定第 $i$ 个摄像头，他需要支付 $c_i$ 美元来完成这次黑客攻击。Skywalkert 会在偷走苹果并卖掉后支付所有黑客攻击的费用。

请编写一个程序，帮助 Skywalkert 在不被抓住的前提下获得尽可能多的利润。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10\,000$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 300\,000$)，分别表示节点数和摄像头数。

第二行包含 $n-1$ 个整数 $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$)，表示节点 $2, 3, \dots, n$ 的父节点。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示节点 $1, 2, \dots, n$ 上的苹果数量。

接下来的 $m$ 行，每行包含三个整数 $x_i, k_i$ 和 $c_i$ ($1 \le x_i \le n, 0 \le k_i \le n, 1 \le c_i \le 10^9$)，表示每个摄像头的参数。

保证所有测试用例的 $n$ 之和不超过 $10^6$，所有测试用例的 $m$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 Skywalkert 可以获得的最大美元金额。

样例

样例输入 1

1
6 3
1 1 2 2 3
2 5 4 3 3 2
2 1 3
3 1 7
1 2 4

样例输出 1

6