U446858 炮兵游击

**L国和Y国~~因为一点鸡毛蒜皮的小事~~打了起来！场面轰轰烈烈！**

你作为$Y$国的参谋长，全权负责本次炮兵活动。现在，你们决定出动1门大炮，这个大炮适合游走，能潜伏于各个区域而不被人发现。你带着这个任务，与那炮秘密潜伏入了敌阵地中。 敌阵地是一个树形阵地，你们有足够的能力能将炮放在任意一个节点上而不被发现。炮的射程为$k(k \leq 20)$个距离单位，一个距离单位是相邻两个结点的间隔距离，且那炮必须按照树的路径走（节省炮弹），每一个结点都有销毁他所得的价值$val_i(val_i \leq 100)$,现在你想知道，将炮放在第$i$个点上时，能获得的价值和$m_i$最多是多少。

- 第一行两个正整数$n,k$，表示敌阵地一共有$n$个结点，炮弹的射程为$k$。 - 第$2$行到第$n$行每行两个正整数$x,y$，表示结点$x,y$之间存在一条路径。 - 第$n+1$到第$2×n$行，每行一个正整数$val_i$，表示炸掉第$i$个结点的价值。

- 共$n$行，每行一个整数$m_i$，表示在第$i$个结点设炮获得的总价值。

- 对于$100\%$的数据，$n \leq 2×10^5,2 \leq k \leq 20,1 \leq val_i \leq 100$ - 对于测试点$1,2$，$1 \leq n \leq 1000,1 \leq k \leq 5$ - 对于测试点$4$，$n \leq 5×10^3,k \leq 10$ - 对于测试点$5$，$k == 1$