• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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

خروجی🔗

در ﺗﻨﻬﺎ ﺳﻄﺮ ﺧﺮوجی، ﺑﯿﺸﺘﺮﯾﻦ ﺗﻌﺪاد ﺳﯿﺒﯽ ﮐﻪ درﺳﺎل می‎ﺗﻮان ﺗﻮﻟﯿﺪ ﮐﺮد را ﭼﺎپ ﮐﻨﯿﺪ.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

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

• محدودیت زمان:‌ ٢ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

مهسا در بازی فرار از خانه غول‌ها شرکت کرده‌است! روال بازی این است که شما ابتدا درون خانه قرار می‌گیرید و باید از غول‌ها فرار کنید و از خانه بیرون بیایید. اما مهسا می‌خواهد به‌جای فرار از غول‌ها، آن‌ها را به تسخیر در آورد!

در این خانه‌ $n$ غول وجود دارد. غول $i$ ، $a_i$ قدرت دارد و اگر مهسا بخواهد آن غول را به تسخیر در بیاورد، یا باید حداقل $b_i$ ( $a_i \le b_i$ ) قدرت داشته باشد، یا $c_i$ تومن به غول پول بدهد. قدرت مهسا ابتدا صفر است. قدرت هر غولی که مهسا تسخیر کند به او اضافه می‌شود؛ یعنی اگر او غول $i$ را تسخیر کند، قدرت او به اندازه‌ی $a_i$ زیاد می‌شود.

مهسا برای خارج شدن از خانه غول‌ها، باید همه غول‌ها را تسخیر کند. او از آن‌جایی که برای ورود به بازی، هزینه‌ی بسیار زیادی پرداخته نمی‌خواهد هزینه‌ی زیادی برای تسخیر غول‌ها بپردازد؛ بنابراین از شما می‌خواهد که کمترین هزینه‌ی لازم برای تسخیر همه غول‌ها را بدست آورید.

ورودی🔗

در سطر اول ورودی عدد $n$، تعداد غول‌ها آمده‌است.

سپس در $i$ امین سطر از $n$ سطر بعدی، سه عدد $a_i$، $b_i$ و $c_i$ آمده‌است که به ترتیب برابر با قدرت غول $i$، قدرت لازم برای تسخیر غول $i$ و هزینه‌ی تسخیر غول $i$ است.

$1 \le n \le 2\ 000$ $0 \le a_i \le b_i \le 2\ 000$ $1 \le c_i \le 2\ 000$

خروجی🔗

در تنها سطر خروجی کمترین هزینه لازم برای تسخیر کردن همه‌ی غول‌ها را چاپ کنید.

زیرمسئله‎ها🔗

مثال🔗

ورودی نمونه ۱🔗

3
1 2 1
1 3 2
2 2 10

خروجی نمونه ۱🔗

3

ورودی نمونه ۲🔗

4
2 3 4
3 4 5
4 5 6
5 6 7

خروجی نمونه ۲🔗

5

• محدودیت زمان:‌ ٢ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

سابیرا در کشور قزاقستان زندگی می‌کند. این کشور از $n$ شهر با شماره‌های $0$ تا $n-1$ تشکیل شده‌است که با $m$ جاده دوطرفه به هم وصل شده‌اند. جاده‌ی $i$-ام دو شهر $u_i$ و $v_i$ را به هم وصل می‌کند. کریسمس نزدیک است و او می‌خواهد به قوم و خویش خود سر بزند.

او در شهر $x$ زندگی می‌کند؛ اقوام پدری او در شهر $y$ و اقوام مادری او در شهر $z$ زندگی می‌کنند. او می‌خواهد برای تعطیلات از شهر خود $x$ به شهر اقوام پدری $y$ و سپس به شهر اقوام مادری $z$ برود و در نهایت به خانه‌اش در شهر $x$ بازگردد.

به علت بارش سنگین برف و ناآشنا بودن سابیرا با جاده‌ها، عبور از جاده‌ی $i$ -ام برای بار اول $a_i$ دقیقه طول می‌کشد و بارهای بعد (مستقل از جهت حرکت روی جاده) $b_i$ دقیقه طول خواهد کشید ($a_i \ge b_i$).

سابیرا برای اینکه بیشتر در کنار اقوامش باشد می‌خواهد کمترین زمان را در جاده‌ها سپری کند. کمترین زمان سپری‌شده در جاده‌ها را پیدا کنید.

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $m$ آمده‌است.

در سطر بعد به‌ترتیب سه عدد $x$، $y$ و $z$ آمده‌است.

در $i$ امین سطر از $m$ سطر بعدی به‌ترتیب چهار عدد $u_i$، $v_i$، $a_i$ و $b_i$ آمده‌است. $3 \le n \le 500$ $2 \le m \le \frac{n \times (n-1)}{2}$ $0 \le x, y, z < n$ $0 \le u_i, v_i < n$ $0 \le b_i \le a_i \le 10^9$

هیچ جاده‌ای یک شهر را به خودش وصل نمی‌کند.

بین هر دو شهر حداکثر یک جاده‌است.

سه شهر $x$ و $y$ و $z$ متفاوت هستند.

تضمین می‌شود که مسیری از $x$ به $y$ و از $x$ به $z$ وجود دارد.

خروجی🔗

در تنها سطر خروجی زمان کوتاه‌ترین سفر ممکن را چاپ کنید.

زیرمسئله‎ها🔗

مثال🔗

ورودی نمونه ۱🔗

5 6
0 1 2
0 1 20 15
0 3 7 2
3 4 4 4
4 1 10 5
4 2 15 15
2 3 14 13

خروجی نمونه ۱🔗

57

در مثال بالا، ترتیب پیمایش بهینه شهرها $\{0, 3, 4, 1, 4, 2, 3, 0\}$