Paprike

Ο Kreso πήγε σε μια τοπική οικογενειακή φάρμα και αγόρασε ένα μάτσο καυτερές πιπεριές που συνδέονται όμορφα με κομμάτια από σπάγκο σχηματίζοντας ένα στεφάνι. Σε αυτό το πρόβλημα, ένα στεφάνι αποτελείται από n πιπεριές και ~(n - 1)~ κομμάτια σπάγκου. Κάθε κομμάτι σπάγκου συνδέει δύο διαφορετικές πιπεριές και κάθε δύο πιπεριές στο στεφάνι συνδέονται (άμεσα ή έμμεσα) από τον σπάγκο. Επομένως, οι πιπεριές και τα κομμάτια του σπάγκου σχηματίζουν ένα λεγόμενο δέντρο. Κάνοντας ένα κόψιμο με ψαλίδι, ο Kreso μπορεί να κόψει τον σπάγκο και να χωρίσει ένα στεφάνι πιπεριάς σε δύο μικρότερα στεφάνια, τα οποία μπορούν και πάλι να χωριστούν σε μικρότερα στεφάνια, και ούτω καθεξής. Παρατηρήστε ότι μία μόνο πιπεριά που δε συνδέεται με οτιδήποτε σχηματίζει επίσης ένα στεφάνι.

Τα αρχικά στεφάνια από τα δύο πρώτα αρχεία ελέγχου μαζί με τα βέλτιστα κοψίματα.

Η καυστικότητα μιας πιπεριάς μετριέται χρησιμοποιώντας τη λεγόμενη κλίμακα Scoville και αναπαρίσταται ως μη αρνητικός ακέραιος αριθμός. Η καυστικότητα του στεφανιού είναι το άθροισμα των καυστικοτήτων των μεμονωμένων πιπεριών που περιέχει. Ο Kreso θέλει να εμπλουτίσει το μεσημεριανό γεύμα των μαθητών γυμνασίου μετά από έναν διαγωνισμό πληροφορικής και ξέρει ότι ο μέσος μαθητής γυμνασίου μπορεί να φάει ένα στεφάνι του οποίου η καυστικότητα είναι το πολύ ~k~ πριν χρειαστεί να ζητήσει γιατρό και δικηγόρο ανηλίκων.
Προσδιορίστε τον ελάχιστο αριθμό κοπών που απαιτούνται ώστε ο Kreso να μπορεί να χωρίσει το αρχικό στεφάνι σε στεφάνια με καυστικότητα το πολύ ~k~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~n~ και ~k~ - τον αριθμό των πιπεριών και τη μέγιστη επιτρεπόμενη καυστικότητα ενός μεμονωμένου στεφανιού. Οι πιπεριές συμβολίζονται με αριθμούς από το ~1~ έως το ~n~. Η παρακάτω γραμμή περιέχει ~n~ ακέραιους αριθμούς ~h_1,\,h_2, \cdots,\,h_n~ - ο αριθμός ~h_j~ είναι η καυστικότητα της πιπεριάς ~j~. Κάθεμια από τα παρακάτω ~n - 1~ γραμμές περιέχει δύο διαφορετικούς ακέραιους ~x~ και ~y (1 \le x,\,y \le n)~- τα "ονόματα" των πιπεριών που συνδέονται απευθείας με ένα κομμάτι σπάγκου στο αρχικό στεφάνι. Οι πιπεριές και οι σπάγκοι σχηματίζουν ένα δέντρο, όπως περιγράφεται στην εργασία.

Έξοδος

Πρέπει να εκτυπώσετε τον ελάχιστο αριθμό κοψιμάτων.

Βαθμολογία

Σε όλα τα υποπροβλήματα, ισχύει ~n \ge 2~, ~0 \le h_1,\,h_2 , \cdots,\,h_n \le k \le 3\,000\,000~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	11	~n \le 15~
2	13	~n \le 100\,000~, κάθε πιπεριά ~x = 1, \cdots ,\,n-1~ είναι συνδεδεμένη με την πιπερία ~x+1~
3	27	~n \le 1\,000~
4	49	~n \le 100\,000~

Παραδείγματα

input

5 5
1 2 3 4 5
1 2
2 3
3 4
4 5

output

3

input

10 10
3 4 2 3 7 1 4 1 5 2
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10

output

3

input

6 9
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6

output

2