Masala E

Imperator tashkil qilgan imperiyada \(N\) ta shahar bor, shaharlar \(1\) dan \(N\) gacha sonlar bilan belgilangan, va bu shaharlarni bog'lab turadigan \(N\) ta yo'l bor. Bu yo'llar orqali barcha shaharlar o'zaro bog'langanligi kafolatlanadi. 

Imperiyaning barcha aholisi shaharlarda istiqomat qilishadi, \(i(1 \le i \le N)\) - shaharda \(A_i\) ta aholi (soliq to'lovchi) istiqomat qiladi.

Imperatorning ikki o'g'li bor. Imperator vafotidan so'ng o'g'illari taxt uchun talashmasin degan maqsadda vafotidan oldin ularga vasiyat yozib qoldirmoqda.

Uning vasiyati quyidagicha:

O'g'illarim imperiyani kelishgan holda ikkiga bo'lib oling, ya'ni, ayrim shaharlar katta o'g'limga, qolgani esa kichik o'glimga bo'lsin.  

Shaharlarni shunday taqsimlangki har biringiz o'zingizga ajratilgan ixtiyoriy bir shahardan boshqa bir shaharingizga o'zingizga tegishli shaharlar orasidagi yo'llar orqali bora oling.

Bo'linish adolatli bo'lishi uchun har ikkalangizning umumiy soliq to'lovchilaringiz soni orasidagi farq mumkin qadar kichik bo'lsin, tabbiiyki bu farqni nol tenglashtirishning imkoni bo'lmasa katta o'g'limga ko'proq soliq to'lovchi qolsin.

Kirish faylining dastlabki satrida bitta butun son, \(N (3 \le N \le 10^5)\) soni, imperiyadagi shaharlar soni kiritiladi.

Ikkinchi satrda \(N\) ta butun son, \(A(1 \le A_i \le 10^9)\)-har bir shahardagi soliq to'lovchilar soni kiritiladi. 

Keyingi \(N\) ta satrda ikkitadan butun son, navbatdagi yo'l qaysi ikki shaharni bog'lab turishi kiritiladi.

Imperatorning o'g'illari shaharlarni otasining vasiyati asosida bo'lib olishsa o'g'illarning soliq to'lovchilari soni orasidagi farq eng kamida nechchi bo'lishini aniqlang.