题目描述

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\)。