The Gu of love is a mystical substance produced only in the Southern kingdom of China. The princess of the Southern Kingdom wishes to use it to revive her love, Pingchiu Yuechu. To experiment, she has collected a group of people, some of whom know each other. She notices that the connections between these groups of people form a tree structure.

She wants to divide these people into exactly $K$ groups, such that the total absolute difference between the number of males and females in each group is as large as possible. Moreover, each person in each group must know each other person in the group directly or indirectly (through multiple connections between other people in the group).

Given $N$, the number of people, and $K$, the number of groups ($1\le K\le N\le 200$), each person's gender and $N-1$ connections between them, figure out this value.

Input Specification

Line 1: Two integers $N$ and $K$ ($1\le K\le N\le 200$)
Line 2: $N$ integers, either $1$ or $0$, the gender of the $i^{\text{th}}$ person.
Next $N-1$ Lines: Two integers $a_j$ and $b_j$, signifying that $a_j$ and $b_j$ are connected.

Sample Input

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

Sample Output

5