Description

The CFF cave consists of n caverns connected by n-1 passageways. For every pair of caverns, there is a unique path from one to the other without leaving the cave. Explosives are placed in certain caverns. Each passageway has a fuse attached. In every cavern, the fuses of adjacent passageways meet at a single point, and if the cavern contains explosives, they are connected to the explosives. The time it takes for the fire to burn through the fuse between two adjacent caverns is exactly one unit of time. Moreover, as soon as the fire reaches a cavern containing explosives, the explosives will immediately detonate.

We want to ignite the fuses at m caverns (igniting at the intersection point of the fuses) so that after ignition, all explosives detonate in the shortest possible time. Write a program to determine this minimum possible time.

Input Format

The first line contains two integers n and m, representing the number of caverns in the cave and the number of fuses that can be ignited, respectively.
The next line contains n integers d~i~, where d~i~=1 indicates that cavern i contains explosives, and d~i~=0 indicates it does not.
The following n-1 lines each contain two integers a and b, representing a passageway connecting caverns a and b.

Output Format

A single integer representing the minimum time required to detonate all explosives.

7 2
1 0 1 1 0 1 1
1 3
2 3
3 4
4 5
5 6
5 7

1

Hint

【Sample Explanation】 We can ignite the fuses in caves 3 and 5. The explosives in cave 3 are detonated at time 0, while the explosives in caves 1, 4, 6, and 7 are detonated one unit of time later.

【Data Range】 For all data, 1 ≤ m ≤ n ≤ 3 × 10^5^, d_i ∈ {0,1}, 1 ≤ a < b ≤ n;
For 10% of the points, n ≤ 10;
For 40% of the points, n ≤ 10^3^.

Source

Adapted from POI 2011 problem.