Maximizing Path Length in a Colored Tree

You are given a tree with n nodes numbered from 1 to n. Each node is colored either black or white. You are allowed to choose any two nodes s and t and traverse the unique simple path between them (i.e. no vertex is visited more than once). However, along the path you are permitted to visit at most k black nodes. Your task is to determine the maximum number of nodes that can be visited on such a path.

Note: The colors are represented as integers where 1 denotes a black node and 0 denotes a white node.

Input Constraints: You may assume that the tree has a small number of nodes so that an exhaustive search solution is acceptable.

inputFormat

The first line contains two integers n and k — the number of nodes in the tree and the maximum number of black nodes allowed on the chosen path, respectively.

The second line contains n space-separated integers, where the i-th integer is either 0 or 1 representing the color of node i (0 for white and 1 for black).

Each of the following n-1 lines contains two integers u and v indicating that there is an edge connecting the nodes u and v.

outputFormat

Output a single integer — the maximum number of nodes that can be visited along a path that contains at most k black nodes.

sample

3 1
1 0 1
1 2
2 3

2