tree-median

Borys likes to travel.
Now he has a vacation and wants to visit beautiful city Treebourg.
The city consists of n junctions and n-1 roads between them.
Treebourg is the best city for tourists because every junction contains an interesting sight to see.
As Treebourg was designed especially for tourists, there are no unnecessary roads — there is exactly one simple path between each pair of junctions (there is exactly one way to travel between a pair of junctions).

Borys also likes solving problems. Mayor of Treebourg is concerned about how interesting sightseeing tours in his city are. He asks Borys to help to make the tours more interesting.

Borys explored the sights and assigned each of them one integer, describing its beauty.
The i-th junction has a sight with beauty b_i.

Each tour is a simple path between some two distinct junctions.
So, there are \frac{n \cdot (n-1)}{2} tours in total.
A tour is considered interesting if the median (definition) of beauties of all sights in the tour is at least x.
If the number of sights is even then the median is greater of two middle values (any of them in case of a tie).
So, the median of (10, 20, 30, 40) is 30.
The median of (10,11,11,12) is 11.
The median of (10, 20, 30) is 20.

The city can allocate money on repairing at most one sight — its beauty will then increase to any value Mayor chooses.
Borys wants to solve the problem optimally.
He wants to repair a sight, in order to maximize the number of new interesting tours.
Help him to do that.

Find the maximum number of tours that become interesting.

Input format
The first line of the input contains two integers n and x — the number of junctions and the treshold for the tour to be interesting, respectively.

Next n - 1 lines describe the roads of Treebourg.
Each of them contains two integers — junctions connected by a road.
Junctions are numbered 1 through n.

The last line of the input contains n integers b_1, b_2, \ldots, b_n — beauties of sights.

Output format
Print a single integer — the maximum difference between the number of interesting tours after the repair and the initial number of interesting tours.

Constraints

2 ≤ n ≤ 300\,000
0 ≤ x, b_i ≤ 10^9

SAMPLE INPUT
3 3
1 2
2 3
1 2 3

SAMPLE OUTPUT
2

Source: hackerearth | Difficulty: HARD
Tags: Complete search


Solutions: