题目描述

X 国有 $n$ 座城市，由 $n-1$ 条道路连接形成了一棵树，每条边都有边权 $w_i$ 表示经过这条边需要 $w_i$ 的时间。为了方便出行，X 国计划在每座城市建造一座传送装置，它们两两之间可以进行传送。传送并不是即时的，初始时你需要给每个传送装置设置一个参数 $a_i$，从装置 $i$ 传送到装置 $j$ 需要花费 $|a_i-a_j|$ 的时间。
X 国并不希望得不偿失的情况发生，因此不能有任意两个城市之间通过传送需要的时间超过走路时间。同时，由于传送装置受每个城市的地质情况限制，每个城市的传送装置参数 $a_i$ 只能是区间 $[l_i,r_i]$ 之内。当然你也可以对城市的地质进行改造，花费 $x$ 的代价可以使所有城市能接受的参数区间扩大为 $[l_i-x,r_i+x]$。代价必须是一个非负整数。
问在不进行改造的情况下，能否找到一种安排 $a_i$ 的方案，满足上述所有要求。有时你还需要回答在允许进行改造的情况下，最少花费多少代价进行改造，可以找到一种方案满足要求（如果不需要改造就可满足则输出 $0$）。

输入格式

第一行两个整数 $t,typ$，表示数据组数和数据类型。
对于每组数据，第一行一个整数 $n$ 表示城市的数量。
接下来一行 $n$ 个整数，第 $i$ 个表示 $l_i$。
接下来一行 $n$ 个整数，第 $i$ 个表示 $r_i$。
接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示一条道路连接 $u$ 和 $v$，权值为 $w$。

输出格式

对于每组数据，如果 $typ=0$，则输出一行一个 $0$（可以满足要求）或 $1$（不满足要求）。
如果 $typ=1$，则输出一行一个整数表示需要的最小代价。

样例

样例输入

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

样例输出

2

数据范围与提示

对于 $20\%$ 的数据，$1\le n\le 5;w,|l_i|,|r_i|\le 8$。
对于 $40\%$ 的数据，$1\le n\le 70$。
对于 $65\%$ 的数据，$1\le n\le 1\ 000$。
对于额外 $15\%$ 的数据，保证 $w=0$。
对于 $100\%$ 的数据，保证 $1\le t\le 3;typ\in\{0,1\};1\le n\le 10^6;0\le w,|l_i|,|r_i|\le 10^9$。
在所有测试点内，均匀分布着约 $20\%$ 的数据，保证 $typ=0$。