有一棵包含 $n$ 个顶点的树，顶点编号为 $1, 2, \dots, n$。在 1 号顶点处有 $m$ 只乌龟。每只乌龟可以在树的无向边上爬行以到达其他顶点。由于乌龟非常重，对于第 $i$ 条边，在被乌龟经过 $k_i$ 次后，该边就会断裂，此后乌龟无法再通过。注意，多只乌龟可以在同一时刻通过同一条边。假设有 $cnt$ 只乌龟在同一时刻通过同一条边，则该边被经过的次数应计为 $cnt$ 次。当然，不允许 $cnt > k_i$ 的情况发生。

你的任务是指挥这 $m$ 只乌龟的移动，使得对于第 $i$ 个顶点（$2 \le i \le n$），至少有 $c_i$ 只乌龟访问过该顶点。注意，如果一只乌龟多次访问同一个顶点，它只会被计算一次。请找到一种移动方案，使得所有乌龟移动的总距离最小，或者判断这是不可能的。

输入格式

第一行包含两个整数 $n$ 和 $M$（$2 \le n \le 10^4, 1 \le M \le 10^4$），分别表示顶点数量和 $m$ 的上限。

接下来的 $n-1$ 行，每行包含四个整数 $u_i, v_i, l_i$ 和 $k_i$（$1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le l_i, k_i \le 10^9$），表示 $u_i$ 号顶点和 $v_i$ 号顶点之间有一条长度为 $l_i$ 的无向边，该边在被经过 $k_i$ 次后会断裂。保证这些边构成一棵树。

最后一行包含 $n-1$ 个整数 $c_2, c_3, \dots, c_n$（$1 \le c_i \le M$），表示每个顶点需要被访问的最小乌龟数量。

输出格式

输出 $M$ 行，第 $i$ 行（$1 \le i \le M$）包含一个整数，表示当 $m=i$ 时的最小总距离。如果无法找到可行的移动方案，请输出 “-1”。

样例

样例输入 1

4 2
1 2 3 2
2 3 2 1
2 4 5 1
1 1 1

样例输出 1

-1
13

样例输入 2

4 2
1 2 3 2
2 3 2 1
2 4 5 1
2 2 2

样例输出 2

-1
-1

说明

在第一个样例中，当 $m=1$ 时，不可能让一只乌龟同时到达顶点 3 和顶点 4。当 $m=2$ 时，最小化总距离的一种可行方案是让两只乌龟都从顶点 1 移动到顶点 2，然后让第一只乌龟移动到顶点 3，让第二只乌龟移动到顶点 4。两只乌龟移动的总距离为 $(3 + 2) + (3 + 5) = 13$。