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 x1 to xp denotes his score in successive matches in world cup. Let the path be x1,x2,x3,...,xp, so Virat wants to find the largest path such that the runs scored in the matches x1,x(1+k),x(1+2*k)... are in non decreasing order.
Help Virat in finding the maximum number of matches he can play.
First line contain the value of N and K.
The next N lines contain the value for each node of the tree where ith line denotes the value for ith node.
After that, the next N-1 lines contain two numbers which specify the nodes between which an edge is present.
Output the maximum number of matches Virat can play.
2<=N<=50000 1<=K<=10 1<=runs_scored_in_a_match<=20 [ Note that virat kohli is in very poor form :-( ] Example Input: