Through the Desert

Φανταστείτε ότι είστε ένας εξερευνητής που προσπαθεί να διασχίσει μια έρημο. Πολλοί κίνδυνοι και εμπόδια παραμονεύουν στο δρόμο σας. Η ζωή σας εξαρτάται από το αν το παλιό καλό σας τζιπ έχει αρκετά μεγάλη δεξαμενή καυσίμου. Αλλά πόσο μεγάλη πρέπει να είναι ακριβώς; Υπολογίστε τον μικρότερο όγκο που απαιτείται για να φτάσετε στο στόχο σας στην άλλη πλευρά.

Τα παρακάτω συμβάντα περιγράφουν το ταξίδι σας:

~Fuel\;consumption\;n~
σημαίνει ότι το φορτηγό σας χρειάζεται ~n~ λίτρα βενζίνης ανά ~100~ χιλιόμετρα -~n~ είναι ένας ακέραιος αριθμός στο εύρος ~[1..30]~. Η κατανάλωση καυσίμου μπορεί να αλλάξει κατά τη διάρκεια του ταξιδιού σας, για παράδειγμα όταν ανεβαίνετε ή κατεβαίνετε ένα βουνό.

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

Ωστόσο, δεν είναι όλα τα συμβάντα ενοχλητικά σε αυτή την έρημο. Τα παρακάτω συμβάντα αυξάνουν τις πιθανότητες επιβίωσής σας:

~Gas\;station~
σας επιτρέπει να γεμίσετε τη δεξαμενή του καυσίμου.

~Mechanic~
διορθώνει όλες τις διαρροές στη δεξαμενή του καυσίμου.
Και τέλος:

~Goal~
σημαίνει ότι έχετε φτάσει με ασφάλεια στο τέλος του ταξιδιού σας!

Είσοδος

Η είσοδος αποτελείται από μια σειρά αρχείων ελέγχου. Κάθε αρχείο ελέγχου αποτελείται το πολύ από ~50~ συμβάντα. Κάθε συμβάν περιγράφεται από έναν ακέραιο αριθμό, την απόσταση (σε χιλιόμετρα, μετρούμενη από την αφετηρία) όπου συμβαίνει το συμβάν, ακολουθούμενη από τον τύπο του συμβάντος όπως περιγράφεται παραπάνω.

Σε κάθε αρχείο ελέγχου, το πρώτο συμβάν είναι της μορφής '~0\;Fuel\;consumption\;n~' και το τελευταίο συμβάν είναι της μορφής '~d\;Goal~' (~d~ είναι η απόσταση από τον στόχο).

Τα συμβάντα δίνονται σε ταξινομημένη σειρά κατά μη φθίνουσα απόσταση από την αφετηρία, και το συμβάν "~Goal~" είναι πάντα το τελευταίο. Μπορεί να υπάρχουν πολλαπλά γεγονότα στην ίδια απόσταση - επεξεργαστείτε τα με τη σειρά με τη σειρά που δίνονται.

Η είσοδος τερματίζεται με μια γραμμή που περιέχει '~0\;Fuel\;consumption\;0~' η οποία δεν πρέπει να επεξεργαστεί.

Έξοδος

Για κάθε αρχείο ελέγχου, εκτυπώστε μια γραμμή με τον μικρότερο δυνατό όγκο δεξαμενής καυσίμου (σε λίτρα, με ακρίβεια τριών δεκαδικών ψηφίων) που εγγυάται ένα επιτυχές ταξίδι.

Παράδειγμα

input

0 Fuel consumption 10
100 Goal
0 Fuel consumption 5
100 Fuel consumption 30
200 Goal
0 Fuel consumption 20
10 Leak
25 Leak
25 Fuel consumption 30
50 Gas station
70 Mechanic
100 Leak
120 Goal
0 Fuel consumption 0

output

10.000
35.000
81.000