Description

请忽略上面的鬼话，就当什么也没看见

一句话题意，给定一颗 $n$ 个点的树，树上每个点不是黑色就是白色，每个点有两个属性 $a$ 和 $b$。

现在多组询问，每次询问仅给出一个参数 $k$，要求你从树上找出一条路径 $(u,v)$ 使得 $u$ 和 $v$ 的颜色不同并且

$$k\times \sum_{p \in path (u-v)}p.a+\sum_{p\in path(u-v)}p.b$$

最大，对于每个询问你仅需要输出这个最大值即可（式子里面的两个和式的意思分别是路径上的点 $a$ 属性之和和路径上点的 $b$ 属性之和）。

tips: $a,b,k$ 均可正可负，并且我们不允许你不选路径，也就是说我们求出的的最大值可以是一个负数，这会发生在所有合法路径的权值都是负数的时候。

Input Format

第一行两个正整数 $n,m$ 表示树的节点个数和询问次数。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的 $a$ 属性的值。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的 $b$ 属性的值。

接下来一行 $n$ 个整数，每个数要么为 $0$ 要么为 $1$，第 $i$ 个数为 $0$ 表示第 $i$ 个点是一个白色点，为 $1$ 表示第 $i$ 个点是一个黑色点。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示存在一条从点 $u$ 到点 $v$ 的边。

接下来 $m$ 行，每行一个整数 $k$ 表示询问的参数。

Output Format

输出 $m$ 行，对于每一个询问，输出题目中给出式子的最大值。

15 15
29 -23 -14 -50 -13 -23 5 33 50 32 27 27 -9 -42 -11
-37 39 21 50 10 -42 -2 25 1 28 40 -45 -24 -29 47
0 0 1 0 0 1 1 0 0 1 0 1 0 0 0
2 1
3 1
4 3
5 2
6 2
7 2
8 4
9 1
10 2
11 5
12 3
13 5
14 3
15 9
-8
36
44
29
-5
-4
-3
-2
-1
0
1
2
3
4
5

679
3252
3988
2608
436
355
274
199
135
126
155
232
309
386
471

Hint

$2 \leq n\leq 10^5$，$1 \leq m \leq 10^5$，$-10^8 \leq k \leq 10^8$

保证不会存在所有点都是黑色或者都是白色的数据，保证对于树上的任意路径，路径上点的 $a$ 属性之和的绝对值不超过$1.5×10^9$，路径上点的 $b$ 属性之和的绝对值不超过 $1.5×10^9$。