Nutrient Tree

Υπάρχει ένα δυαδικό δέντρο με ~l~ φύλλα ~(1 \le l \le 50)~, όπου κάθε φύλλο ~k~ παράγει μια ποσότητα θρεπτικών ουσιών ~n_{k}\;(1 \le n_{k} \le 10000)~.

Τα κλαδιά (τα οποία μπορείτε να φανταστείτε ως ακμές) αυτού του δυαδικού δέντρου, περιορίζουν τη μέγιστη ποσότητα θρεπτικών ουσιών που μπορεί να ρεύσει προς τη ρίζα του δέντρου. Έχετε ~X~ αυξητικούς παράγοντες ~(1 \le X \le 2500)~ που μπορούν να χρησιμοποιηθούν για να αυξήσουν το πάχος μιας ακμής ή να αυξήσουν την παραγωγή θρεπτικών ουσιών ενός κόμβου φύλλου. Αρχικά, κάθε ακμή έχει βάρος ~1~ και αν της δώσετε ~w~ αυξητικούς παράγοντες τότε θα μπορεί να μεταφέρει ~(1 + w)^2~ θρεπτικά συστατικά. Η αύξηση της παραγωγής θρεπτικών συστατικών ενός φύλλου με αρχική τιμή ~n_{k}~ κατά ~s~, αυξάνει την παραγωγή θρεπτικών συστατικών αυτού του φύλλου σε ~n_{k} + s~.

Παρατηρήστε ότι όταν οι ακμές συναντώνται, η ποσότητα των θρεπτικών ουσιών που ρέει είναι το άθροισμα των θρεπτικών ουσιών που ρέουν κατά μήκος των ακμών αυτών.

Βρείτε τη μέγιστη ποσότητα θρεπτικών ουσιών που μπορείτε να μεταφέρετε ως τη ρίζα.

Είσοδος

Η πρώτη γραμμή της εισόδου θα είναι μια περιγραφή του δέντρου. Αυτή η περιγραφή μπορεί να οριστεί αναδρομικά (recursively) είτε ως ακέραιος ~n_{k}\;(1 \le n_{k} \le 10000)~ είτε ως ~(T_{L}T_{R})~ όπου ~T_{L}~ και ~T_{R}~ είναι περιγραφές του αριστερού και του δεξιού υποδέντρου, αντίστοιχα. Η δεύτερη γραμμή της εισόδου θα είναι ο ακέραιος ~X~, το ποσό των αυξητικών παραγόντων που διαθέτετε. Σημείωση: τουλάχιστον το ~30%~ των βαθμών αυτής της ερώτησης έχει ~l \le 5~ και ~X \le 50~.

Έξοδος

Σε μία γραμμή, εξάγετε τη μέγιστη ποσότητα θρεπτικών ουσιών που μπορούν να εισρεύσουν στη ρίζα του δέντρου.

Παράδειγμα

input

(5 ((7 1) (3 4)))
3

output

7

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

Η περιγραφή του δέντρου μπορεί να απεικονιστεί ως εξής:

Παρατηρήστε ότι αν βάλουμε δύο αυξητικούς παράγοντες στην αριστερή ακμή της ρίζας και έναν αυξητικό παράγοντα στη δεξιά ακμή της ρίζας τότε, θα ρέουν ~5~ θρεπτικές ουσίες από το φύλλο με την ένδειξη ~5~ προς τη ρίζα (αφού η χωρητικότητα είναι ~(1 + 2)^{2} = 9~ μονάδες θρεπτικών ουσιών) και ~2~ θρεπτικοί παράγοντες από το δεξί υποδέντρο (δεδομένου ότι η χωρητικότητα είναι ~(1 + 1)^{2} = 4~, αλλά υπάρχουν μόνο ~2~ μονάδες θρεπτικών ουσιών λόγω του ορίου ~1~ στις ακμές που συνδέονται με όλα τα άλλα φύλλα).

Εναλλακτικά, παρατηρήστε ότι αυξάνοντας την παραγωγή θρεπτικών ουσιών του αριστερού φύλλου της ρίζας σε ~6~ και με αύξηση της χωρητικότητας της ρίζας προς το αριστερό φύλλο κατά ~2~ (ώστε να προκύψει χωρητικότητα ~(1 + 2)^{2} = 9~ μονάδες) θα προκαλούσε τη ροή ~6~ μονάδων θρεπτικών ουσιών στη ρίζα από το αριστερό δέντρο και το δεξιό υποδέντρο της ρίζας θα παρήγαγε ~1~ μονάδα θρεπτικής ουσίας.

Και στις δύο περιπτώσεις, η μέγιστη ποσότητα θρεπτικών ουσιών που μπορεί να φτάσει στον κόμβο της ρίζας είναι ~7~.