• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون مقدماتی دوم دوره ۲۷ المپیاد کامپیوتر

---

کروکی درون باغ لیکوئید یک درخت سیب دارد. این درخت از پایین به بالا به شکل یک درخت ریشه دار است. راس‎های درخت از \(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