Masala #BF05BOO0H3

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.