Dostavljač

Από τότε που ο Krešo άρχισε να καλλιεργεί πιπεριές τσίλι, ~N~ εστιατόρια σε όλη την Κροατία έδειξαν ενδιαφέρον για τις πιπεριές του, ώστε να εμπλουτίσουν τα πιάτα τους με αληθινά μπαχαρικά. Λόγω της μεγάλης ζήτησης, ο Krešo αποφάσισε να αρχίσει να εργάζεται ως διανομέας πιπεριών τσίλι.

Τα εστιατόρια συμβολίζονται με αριθμούς από το 1 έως το ~N~ και συνδέονται αμοιβαία με δρόμους ~N - 1~ έτσι ώστε να είναι δυνατή η μετακίνηση μεταξύ δύο εστιατορίων. Ο Krešo ξεκινά το ταξίδι του στο εστιατόριο που δηλώνεται με 1. Σε μία μονάδα χρόνου, μπορεί είτε να οδηγήσει στο διπλανό εστιατόριο είτε να παραδώσει τις πιπεριές στο τρέχον εστιατόριο. Για κάθε εστιατόριο, γνωρίζουμε την απαιτούμενη ποσότητα πιπεριών ~A_i~.

Δεδομένου ότι η παράδοση αγαθών είναι κουραστική, ο Krešo αποφάσισε να αφιερώσει συνολικά ~M~ μονάδες χρόνου για την παράδοση και το ταξίδι, μετά από τα οποία σχεδιάζει να κάνει ένα διάλειμμα. Προσδιορίστε τη μέγιστη ποσότητα πιπεριών που μπορεί να παραδώσει το Krešo στο δεδομένο χρονικό πλαίσιο. Μπορείτε να υποθέσετε ότι το Krešo έχει πάντα απεριόριστη ποσότητα πιπεριών.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς ~N~ και ~M\;(1 \le N, M \le 500)~, τον αριθμό των εστιατορίων και τον χρόνο που σχεδιάζει να αφιερώσει ο Krešo για την παράδοση πιπεριών.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ ακέραιους αριθμούς ~A_i\;(1 \le A_i \le 10^6)~, η απαιτούμενη ποσότητα πιπεριών για εστιατόρια συμβολίζεται με ~i\;(1 \le i \le N)~.
Κάθε μία από τις ακόλουθες γραμμές ~N - 1~ περιέχει δύο ακέραιους αριθμούς ~U~ και ~V\;(1 \le U, V \le N,\;U \ne V)~, που αντιπροσωπεύουν το δρόμο μεταξύ των εστιατορίων.

Έξοδος

Πρέπει να τυπώσετε τη μέγιστη ποσότητα πιπεριών που μπορεί να παραδώσει ο Krešo στο δεδομένο χρονό.

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

input

3 5
9 2 5
1 2
1 3

output

14

Επεξήγηση του 1ου παραδείγματος:

Στο πρώτο βήμα, ο Krešo θα παραδώσει τις πιπεριές στο εστιατόριο 1.
Στο δεύτερο βήμα, ο Krešo θα ταξιδέψει στο εστιατόριο 3.
Στο τρίτο βήμα, ο Krešo θα παραδώσει τις πιπεριές στο εστιατόριο 3.
Του μένουν 2 μονάδες χρόνου, στις οποίες μπορεί να οδηγήσει στο εστιατόριο 2, αλλά του λείπει μία μονάδα χρόνου για να παραδώσει τις πιπεριές σε αυτό το εστιατόριο.

input

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

output

3

input

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

output

15