Krešo je na lokalnom obiteljsko-poljoprivrednom gospodarstvu kupio hrpu ljutih papričica uredno povezanih komadima špage u takozvani vijenac. U ovom zadatku, vijenac se sastoji od n paprika i (n−1)-og komada špage. Svaki komad špage povezuje dvije različite paprike te su svake dvije paprike u vijencu (direktno ili indirektno) povezane špagom. Dakle, paprike i komadi špage čine takozvano stablo. Jednim potezom škara Krešo može prerezati jednu špagu te vijenac paprika rastaviti na dva manja vijenca, koja opet rezovima može rastaviti na manje vijence itd. Primijetite da jedna ni sa čim povezana paprika također čini vijenac.

Ljutina pojedine paprike mjeri se pomoću takozvane Scovillove ljestvice te je izražena nenegativnim cijelim brojem. Ljutina vijenca je suma ljutina pojedinih paprika koje sadrži. Krešo želi zapapriti ručak srednjoškolcima nakon informatičkog natjecanja i zna da prosječni srednjoškolac može pojesti vijenac ljutine najviše k prije nego što mora zatražiti pomoć liječnika i dječjeg pravobranitelja. Odredite najmanji broj rezova potreban da Krešo rastavi početni vijenac na vijence ljutine najviše k.

Ulazni podaci

U prvom redu nalaze se cijeli brojevi n i k — broj paprika i najveća dopuštena ljutina jednog vijenca. Paprike su označene brojevima od 1 do n. Sljedeći red sadrži n cijelih brojeva h1, h2, . . . , hn — broj hj je ljutina paprike j. Svaki od sljedećih n − 1 redova sadrži dva različita prirodna broja x i y (1 ≤ x, y ≤ n) — oznake paprika direktno povezanih špagom u početnom vijencu. Paprike i špage čine stablo kao što je opisano u tekstu zadatka.

Izlazni podaci

Ispišite traženi najmanji broj rezova.