After centuries of warfare against their inflatable archnemesis, the Bloons, the monkeys have finally developed a new technology that they hope will allow them to win: the Sun Temple! Factories everywhere have been put on overdrive during the past few weeks, processing and assembling all the parts necessary to build as many temples as needed in order to defend the realm. More specifically, the monkey world consists of a single giant tree consisting of $N$ cities, conveniently labelled with the integers $1$ through $N$. Among these cities are also $N-1$ tree branches which connect them in such a way that there exists only one unique path of roads between any two cities.

As the kingdom's foremost scientist, you are tasked with scheduling the construction of temples in the vast network of cities. Unfortunately, you've come to realize that there are two critical problems that stand in your way.

1. Sun Temples are large: smaller cities can't even support a single temple, and even the greatest monkey metropolises do not have enough room for more than one temple.

2. When activated, the temples require a lot of solar energy: you've realized that the distance between any pair of temples should always be greater than or equal to a constant, $R$.

This means that the final schematic should not attempt to place temples in invalid cities, and there should be no temple that is within the range of another temple. Can you determine the maximum number of temples that can be safely constructed?

Constraints

Subtask 1 [40%]

$1\le N,R\le 500$

Subtask 2 [60%]

$1\le N,R\le 2\times {10}^5$

Input Specification

The first line of input will contain the integers $N$ and $R$, in that order.

The next $N-1$ lines will contain two integers, $a_i$ and $b_i$, on each line. This will denote the existence of a bi-directional path connecting the two cities.

The final line will contain a string of length $N$. If the $i^{\text{th}}$ character on the string is a 0, it means that the city with index $i$ is unable to host its own sun temple. If it is a 1, then that city is eligible for the construction of a single temple, assuming all other constraints are satisfied.

Output Specification

Output the maximum number of temples that can fit.

Sample Input

7 2
1 2
2 3
3 4
4 5
2 6
4 7
1011101

Sample Output

4

Explanation for Sample Output

The optimal solution is to construct temples in cities with indices $1$, $3$, $5$, and $7$.