Cho một cây gồm ~N~ đỉnh mỗi đỉnh có ~1~ nhãn ~C_i~ gọi là trọng số của đỉnh ~i~. Hãy tìm ~1~ cây con gồm ~P~ đỉnh sao cho tổng trọng số của cây con này là lớn nhất. Hiểu ~1~ cách đơn giản là tìm ~P~ đỉnh sao cho ~P~ đỉnh này liên thông và tổng trọng số là lớn nhất.

Dữ liệu vào

• Dòng 1: chứa hai số nguyên dương ~N, P~ ~(1 ≤ P ≤ N ≤ 200)~.
• Dòng 2: chứa ~N~ số nguyên dương ~C_1, C_2, ..., C_N~ ~(-1000 ≤ A_i ≤ 1000)~.
• ~N - 1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u, v~ mô tả ~1~ cạnh của đồ thị.

Dữ liệu ra

Gồm ~2~ dòng:

• Dòng 1: tổng trọng số lớn nhất.
• Dòng 2: ghi ra ~P~ số nguyên là chỉ số của ~P~ đỉnh được chọn.

Sample Input

3 2
1 2 3
1 2
2 3

Sample Output

5
2 3