+ محدودیت زمان: ۰.۵ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
+ منبع: آزمون مقدماتی دوم دوره ۲۷ المپیاد کامپیوتر
----------
کروکی درون باغ لیکوئید یک درخت سیب دارد. این درخت از پایین به بالا به شکل یک درخت ریشه دار است. راسهای درخت از $0$ تا $n-1$ نام گذاری شدهاند و ریشه این درخت راس $0$ است. کروکی می داند که درختهای سیب تنها در برگها میوه میدهند. جیاچ به او گفته است که اگر راس $i$ برگ باشد در سال $a_i$ تا سیب می دهد. کروکی میخواهد با قیچی باغبانی خود شاخههایی از درخت را ببرد به صورتی که درخت باقیمانده دقیقا $k$ برگ داشته باشد، شامل راس ریشه باشد و تعداد سیبهایی که در سال می دهد بیشینه باشد. به کروکی کمک کنید که این مقدار بیشینه را بدست آورد.
ﺗﻮجه ﮐﻨﯿﺪ ﮐﻪ راس رﯾﺸﻪ ﺗﻨﻬﺎ در ﺻﻮرتی ﺑﺮگ ﺣﺴﺎب میﺷﻮد ﮐﻪ ﺗﻨﻬﺎ راس ﺑﺎﻗﯿﻤﺎﻧﺪه در درﺧﺖ ﺑﺎﺷﺪ.
# ورودی
در ﺳﻄﺮ اول ﺑﻪ ﺗﺮﺗﯿﺐ اﻋﺪاد $n$ و $k$ آمدهاند
در ﺳﻄﺮ دوم $n$ عدد $a_0,a_1,a_2,...,a_{n-1}$ آمدهاست.
در $i$ امین سطر از $n-1$ سطر بعد دو عدد $v_i$ و $u_i$ آمدهاند که نشان دهنده وجود یک شاخه بین راس $v_i$ و $u_i$ در درخت است.
$$ 1 \le n \le 100\ 000$$$$ 1 \le k \le 100$$$$ 1 \le a_i \le 1\ 000\ 000\ 000$$$$ 0 \le v_i,u_i \lt n$$
تضمین میشود شاخههای ورودی تشکیل یک درخت میدهند.
تضمین می شود درخت در ابتدا حداقل $k$ برگ دارد.
# خروجی
در ﺗﻨﻬﺎ ﺳﻄﺮ ﺧﺮوجی، ﺑﯿﺸﺘﺮﯾﻦ ﺗﻌﺪاد ﺳﯿﺒﯽ ﮐﻪ درﺳﺎل میﺗﻮان ﺗﻮﻟﯿﺪ ﮐﺮد را ﭼﺎپ ﮐﻨﯿﺪ.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:-------:|:----------:|:-----------:|
|۱ | ۱۱ | $n \le 20 $|
|۲| ۱۸ | $k \le 2 $ |
|۳| ۲۲ |$n \le 500 $ |
|۴| ۴۹ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه ۱
```
8 3
83 91 9 12 15 11 7 8
0 1
0 2
1 3
1 4
3 5
4 6
4 7
```
## خروجی نمونه ۱
```
36
```
## ورودی نمونه ۲
```
3 1
1 2 3
0 1
0 2
```
## خروجی نمونه ۲
```
3
```
## ورودی نمونه ۳
```
3 1
3 2 1
0 1
0 2
```
## خروجی نمونه ۳
```
3
```