Mravi

Ο μικρός Bobi σηκώνεται κάθε πρωί και ταΐζει τα αγαπημένα του κατοικίδια: τα μυρμήγκια. Τα διατηρεί σε ένα terrarium με σύστημα σωλήνων που μπορεί να αναπαρασταθεί ως δέντρο με ~N~ κόμβους. Οι σωλήνες αντιπροσωπεύονται από τις άκρες του δέντρου. Η ρίζα του δέντρου βρίσκεται στον κόμβο που συμβολίζεται με το 1. Μέσα στο σύστημα σωλήνων, το υγρό ρέει από έναν κόμβο στα παιδιά του λόγω της βαρύτητας.

Γνωρίζουμε τη ροή ~X_i~ κάθε σωλήνα: το ποσοστό του ρευστού από τον γονικό κόμβο που ρέει μέσω αυτού του σωλήνα στον παιδικό κόμβο. Ας παρατηρήσουμε το ακόλουθο παράδειγμα:

Ο κόμβος 1 από την εικόνα έχει 12 λίτρα υγρού και έχει δύο σωλήνες μετά από αυτόν. Το ένα έχει ροή ~X_i = 30~ και το άλλο ~X_i = 70~. Ο κόμβος 2 θα πάρει ~3.6~ λίτρα και ο κόμβος 3 θα πάρει ~8.4~ λίτρα. Στα δεδομένα εισόδου, το άθροισμα των ροών των σωλήνων που πηγαίνουν από τον ίδιο κόμβο θα είναι πάντα ίσο με 100.

Μερικοί από τους σωλήνες του Bobi δεν είναι απλώς κανονικοί σωλήνες. είναι λίγο περίεργα. Είναι σούπερ σωλήνες που έχουν την υπερδύναμη να τετραγωνίζουν την ποσότητα του υγρού που ρέει μέσα τους. Στο προηγούμενο παράδειγμα, εάν ο πρώτος σωλήνας έχει την υπερδύναμη, ο κόμβος 2 παίρνει ~12.96~ λίτρα και ο κόμβος 3 εξακολουθεί να παίρνει μόνο ~8.4~ λίτρα. Παρατηρήστε τώρα ότι ένας κόμβος έχει περισσότερο υγρό που βγαίνει από αυτό από την ποσότητα που εισέρχεται σε αυτόν. Αυτός είναι ακριβώς ο λόγος που αυτοί οι σωλήνες είναι σούπερ σωλήνες!

Όλοι οι σούπερ σωλήνες μπορούν να ενεργοποιήσουν ή να απενεργοποιήσουν την υπερδύναμή τους σύμφωνα με τον Bobi.

Τα μυρμήγκια ζουν μόνο στα φύλλα του δέντρου (κόμβοι που δεν έχουν παιδιά). Για κάθε φύλλο γνωρίζουμε την απαιτούμενη ποσότητα υγρού ~K_i~ για να ταΐσουμε όλα τα μυρμήγκια που ζουν σε αυτό το φύλλο. Ο Μπόμπι θέλει να ταΐσει τα μυρμήγκια του ρίχνοντας ~L~ λίτρα υγρού στη ρίζα του δέντρου. Δεν έχει πολλά χρήματα, επομένως θέλει να γνωρίζει την ελάχιστη ποσότητα λίτρων υγρού που χρειάζεται να αγοράσει για να κρατήσει όλα τα μυρμήγκια του να τρέφονται.

Σημείωση: Τα δεδομένα εισόδου είναι τέτοια ώστε ο απαιτούμενος αριθμός ~L~ δεν θα υπερβαίνει το ~2 \times 10^9~ .

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(1 \leq N \leq 1000)~.

Κάθε μία από τις ακόλουθες ~N-1~ γραμμές περιέχει τέσσερις ακέραιους ~A_i,\;B_i,\;X_i,\;T_i\;(1 \leq A_i ,\;B_i \leq N,\;1 \leq X_i \leq 100,\;0 \leq T_i \leq 1)~ όπου ~A_i~ και ~B_i~ είναι τα άκρα ενός σωλήνα (οι ετικέτες των κόμβων που συνδέονται με τον σωλήνα), το ~X_i~ είναι η ροή του υγρού μέσω του σωλήνα και το ~T_i~ υποδηλώνει εάν ο σωλήνας έχει υπερδύναμη. Εάν το ~T_i~ είναι 1, αυτός ο σωλήνας έχει υπερδύναμη, διαφορετικά δεν έχει.

Η ακόλουθη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~K_i~ που περιγράφουν την ποσότητα του υγρού που απαιτείται για τα μυρμήγκια στον ~i~-οστό κόμβο. Εάν ο ~i~-οστός κόμβος δεν είναι φύλλο, το ~K_i~ θα είναι -1, διαφορετικά θα είναι ακέραιος από το διάστημα ~[1,\;10]~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό από την εργασία.
Σημείωση: Το επιτρεπόμενο απόλυτο σφάλμα από τη σωστή (ακριβή) λύση είναι ~0,001~.

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

input

5
1 2 50 0
1 3 50 0
2 4 25 0
2 5 75 1
-1 -1 4 1 9

output

8.00

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

Αν ο Bobi ρίξει 8 λίτρα υγρού στη ρίζα του δέντρου, ο κόμβος 3 θα πάρει 4 λίτρα, ο κόμβος 4 θα πάρει 1 λίτρο και ο κόμβος 5 θα πάρει 9 λίτρα. Αυτοί οι κόμβοι είναι φύλλα (έχουν μυρμήγκια μέσα τους) και αυτή είναι η ακριβής ελάχιστη ποσότητα που πρέπει να πάρουν τα μυρμήγκια. Επίσης, 8 λίτρα είναι η ελάχιστη ποσότητα υγρού που ικανοποιεί τις συνθήκες "μυρμήγκι".

input

3
1 2 20 1
1 3 80 1
-1 4 8

output

10.0000

input

6
1 2 100 1
2 3 20 0
2 4 20 0
2 5 60 0
4 6 100 1
-1 -1 1 -1 1 2

output

2.659