Ahead of World cup, Virat Kohli goes to a genius astrologer who gives him a tree with

n nodes whose every node specifies the runs Virat scores in a match.

Virat wants to play as many matches in this world cup as possible. Any path from node

x_{1 }to x_{p} denotes his score in successive matches in world cup. Let the path be

x_{1},x_{2},x_{3},...,x_{p}, so Virat wants to find the largest path such that the runs scored in the matches

x_{1},x_{(1+k)},x_{(1+2*k)}... are in non decreasing order.

Help Virat in finding the maximum number of matches he can play.

### Input

###

First line contain the value of N and K.

The next N lines contain the value for each node of the tree where i^{th} line denotes the value for i^{th} node.

After that, the next N-1 lines contain two numbers which specify the nodes between which an edge is present.

### Output

Output the maximum number of matches Virat can play.

Constraints
2<=

N<=

50000
1<=

K<=

10
1<=

runs_scored_in_a_match<=

20 [ Note that virat kohli is in very poor form :-( ]

Example
Input:
5 1

12

11

18

2

20

1 2

1 3

2 4

3 5

Output:
5