题目描述

白乌鸦葡萄园已经荒废了一年多，直到最近女爵的赐封才让它迎来新的主人。

你拥有了一座葡萄园，它的结构是一棵以节点 $1$ 为根的树。

树上每个节点都有一张酒桌。第 $i$ 个节点的桌上摆放着 $a_i$ 瓶葡萄酒，并有 $b_i$ 个人在桌旁闲聊。

现在按照节点深度从大到小的顺序处理各个节点。处理节点 $i$ 时，当前位于节点 $i$ 的人可以选择散步到节点 $i$ 的任意一个祖先节点，也可以留在原地。

庄园的规模有限，因此需要满足以下限制：对于任意祖孙节点对 $(i,j)$，其中 $j$ 是 $i$ 的祖先，从节点 $i$ 移动到节点 $j$ 的人数不能超过 $c$。

记所有移动完成后，第 $i$ 个节点上的人数为 $b'_i$。

如果一个人能够喝到一瓶独属于自己的葡萄酒，他就会感到开心。因此，节点 $i$ 上最多有

个人开心。

请合理安排所有人的移动，使开心人数总和

最大，并输出这个最大值。

输入格式

第一行包含两个正整数 $n,c$。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

第三行包含 $n$ 个非负整数 $b_1,b_2,\ldots,b_n$。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示树中存在一条连接节点 $u$ 与节点 $v$ 的无向边。

输出格式

输出一行一个整数，表示能够得到的最大开心人数。

样例

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

9

数据范围与约定

其中，“菊花图”表示除根节点外的所有节点都直接与根节点相连。