시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 5 3 3 60.000%

문제

You are given a tree of n vertices, each with a unique number from 1 to n. A vertex has a color, black or white. Choose exactly m black vertices so that the length of the longest path between any of them is minimal.

입력

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 100) — the number of vertices and the number of black vertices you have to choose.

The fourth line contains n integers p1, p2, . . . , pn (0 ≤ pi ≤ 1). If the pi = 1, then the i-th vertex is black; otherwise, it is white. It is guaranteed that the number of black vertices is at least m. Each of the next n − 1 lines contains two integers vi and ui (1 ≤ vi , ui ≤ n) meaning that there is an edge between vi and ui.

It is guaranteed that the input graph is a tree.

출력

Print a single integer — the answer to the task.

예제 입력 1

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

예제 출력 1

2

예제 입력 2

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

예제 출력 2

5

힌트

In the first example, the only option is to choose 1, 2, and 4. The maximum distance will be 2.

In the second example, you can choose 1, 3, 8, and 9. The maximum distance will be between 3 and 9.