Masala E

Masala oson bo‘lsa - unga shart kerakmi?
N ta tugundan iborat daraxt mavjud. Bu daraxtning i -tuguni $c_i(1 ≤ c_i ≤ K)$ - rangda bo’yalgan, hamda bu tugunda $a_i(−10^9 ≤ a_i ≤ 10^9)$ soni yozilgan. Siz bu daraxtdan quyidagi shartlarni qanoatlantiradigan ixtiyoriy qism daraxtni ajratib oling:
- Ajratib olingan qism daraxtda kamida 1 ta tugun mavjud bo’lsin
- Ajratib olingan qism daraxtning barcha tugunlari bir xil rangda bo’lsin
- Ajratib olingan qism daraxtdagi barcha tugunlarda yozilgan $a_i$ lar yig’indisi mumkin qadar kattaroq bo‘lsin.

Kirish faylining dastlabki satrida ikkita butun son, $N(1 ≤ N ≤ 2 * 10^5)$ va $K(1 ≤ K ≤ 10^4 )$ sonlari berilgan. Ikkinchi satrda N ta butun son, a massiv elementlari kiritiladi. Uchinchi satrda N ta butun son, c massiv elementlari kiritiladi. Keyingi N − 1 ta satrda ikkitadan butun son, daraxt qirralari kiritiladi.

Chiqish faylining dastlabki satrida ajratib olingan qism daraxtning tugunlarida yozilgan $a_i$ lar yig‘indisini chop eting. Ikkinchi satrda ajratib olingan qism daraxtning elementlari sonini chop eting. Uchinchi satrda ajratib olingan qism daraxt tugunlari raqamini bo‘sh joy bilan ajratgan holda chop eting.