Дано дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. В каждой вершине-листе $$$v$$$ лежит $$$c_v$$$ листиков. В остальных вершинах листиков нет. Если $$$n=1$$$, корень также считается листом.
Вначале все муравьи находятся в корне. Их количество не ограничено. За одну секунду муравей может пройти по одному ребру. Муравьи передвигаются одновременно и не мешают друг другу. Каждый муравей в любой момент времени может нести не более одного листика. Взять листик можно в вершине, где он лежит; доставленным считается только листик, который муравей принёс в корень.
Какое наибольшее количество листиков муравьи могут доставить в корень за $$$T$$$ секунд?
В первой строке даны два целых числа $$$n$$$ и $$$T$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$0\le T\le 10^9$$$).
В следующих $$$n-1$$$ строках даны по два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u,v\le n$$$) — концы ребра. Гарантируется, что рёбра образуют дерево.
В последней строке даны $$$n$$$ целых чисел $$$c_1,c_2,\ldots,c_n$$$ ($$$0\le c_i\le 10^9$$$). Для каждой вершины, не являющейся листом, $$$c_i=0$$$.
Выведите одно целое число — максимальное количество листиков, доставленных в корень не позднее чем через $$$T$$$ секунд. Ответ может не помещаться в 32-битный целочисленный тип.
5 23 21 52 42 10 0 1 1 1
1
1 01
1
Тест 1. За две секунды муравей успеет принести листик из вершины $$$5$$$: одну секунду он потратит на путь к листику и ещё одну — на обратный путь. Листики из вершин $$$3$$$ и $$$4$$$ находятся на расстоянии двух рёбер от корня, поэтому для их доставки нужно четыре секунды.
Тест 2. Все листики уже находятся в корне.
