ACM

Ένας αρχαίος διαγωνισμός προγραμματισμού πλησιάζει και διοργανώνεται από την ACM (Aeronautic Center of Metković). Ακριβώς ~N~ ομάδες θα διαγωνιστούν για το μεγάλο έπαθλο και ανάμεσά τους είναι μια χρυσή τριάδα της Κροατίας: η Paula, ο Marin και ο Josip. Η μορφή του διαγωνισμού είναι στάνταρ, ενώ ο πιλότος εκτελεί ακροβατικούς ελιγμούς, ο συγκυβερνήτης διαβάζει τις δηλώσεις προβλημάτων και επιχειρεί να μεταδώσει τις λύσεις στον κύριο προγραμματιστή που είναι κολλημένος με ασφάλεια στο εξωτερικό του αεροσκάφους.

Ο διαγωνισμός αποτελείται από ~M~ διαφορετικές εργασίες και οι ομάδες ταξινομούνται (όχι όλο και περισσότερο) με βάση τον αριθμό των λυμένων εργασιών.

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

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

Ο διαγωνισμός τελείωσε και η βαθμολογία πρέπει να ξεπαγώσει σύντομα. Οι ήρωές μας, η ομάδα με το όνομα NijeZivotJedanACM χρειάζονται τη βοήθειά σας. Θέλουν να μάθουν ποια είναι η χειρότερη δυνατή θέση στον πίνακα αποτελεσμάτων στην οποία θα μπορούσαν να καταλήξουν αφού η βαθμολογία ξεπαγώσει. Βοήθησέ τους!

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~N\;(1 \le N \le 1000)~ και ~M\;(1 \le M \le 15)~ από την περιγραφή της εργασίας.

Οι επόμενες ~N~ γραμμές αντιπροσωπεύουν την παγωμένη βαθμολογία. Κάθε γραμμή ξεκινά με ένα όνομα ομάδας (συμβολοσειρά που αποτελείται από πεζά και κεφαλαία αγγλικά γράμματα που αποτελείται από το πολύ 20 χαρακτήρες, τα ονόματα όλων των ομάδων θα είναι διαφορετικά) που χωρίζεται με ένα κενό διάστημα από τις συμβολοσειρές ~M~ (επίσης διαχωρισμένες με κενό διάστημα) που κρατούν τις πληροφορίες σχετικά με την κατάσταση κάθε εργασίας για αυτήν την ομάδα.

Αυτές οι συμβολοσειρές είναι της μορφής ~SX/V~, όπου:

• Το ~S~ αντιπροσωπεύει την κατάσταση της εργασίας "+" σημαίνει ότι η εργασία επιλύθηκε σωστά, "-" σημαίνει ότι έχει λυθεί λανθασμένα και "?" σημαίνει ότι η τελευταία υποβολή στάλθηκε όταν οι βαθμολογίες είχαν ήδη παγώσει.
• Το X αντιπροσωπεύει τον αριθμό των υποβολών που στάλθηκαν από αυτήν την ομάδα για τη συγκεκριμένη εργασία. Παραλείπεται εάν δεν υποβλήθηκαν υποβολές για αυτήν την εργασία.
• Το V αντιπροσωπεύει τη στιγμή που στάλθηκε η τελευταία υποβολή από αυτήν την ομάδα για τη συγκεκριμένη εργασία. Δίνεται στη μορφή ΩΩ:ΛΛ:ΔΔ (με μηδενικά στην αρχή) και είναι μικρότερη από 5 ώρες. Ολόκληρο το τμήμα /V παραλείπεται εάν η εργασία δεν λυθεί σωστά (κατάσταση '-')

Η τελευταία γραμμή περιέχει τη μη παγωμένη βαθμολογία των ηρώων μας, της ομάδας που ονομάζεται NijeZivotJedanACM.

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 20 πόντων, η είσοδος δεν θα περιέχει τον χαρακτήρα "?".

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

input

2 1
NijeZivotJedanACM -
ZivotJESTJedanACM -
NijeZivotJedanACM -

output

1

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

Τίποτα δεν θα αλλάξει αφού ξεπαγώσει η βαθμολογία. Επομένως, οι ήρωές μας θα παραμείνουν στην πρώτη θέση!

input

3 2
StoJeZivot ?1/04:00:00 +1/02:04:06
JeLiZivotJedanACM ?1/04:59:59 -
NijeZivotJedanACM ?1/04:42:43 -
NijeZivotJedanACM +1/04:42:43 -

output

2

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

Στη χειρότερη περίπτωση οι ήρωές μας θα χάσουν μόνο από την ομάδα StoJeZivot, τερματίζοντας έτσι στη δεύτερη θέση.

input

7 4
NisamSadaNistaDonio +1/03:59:59 +3/03:42:02 +2/00:14:59 ?1/04:56:12
JeLiMojKockaSeUmio ?4/04:00:00 -3 +1/00:10:01 +9/03:04:42
OstaviDobroJe ?4/04:59:59 -1 +2/00:24:15 +8/03:24:45
DobroJeOstavi +1/01:42:53 - ?9/04:58:23 ?1/04:34:43
NijeZivotJedanACM ?2/04:50:05 ?4/04:32:12 +2/01:32:45 ?1/04:59:59
KoSeToSeta ?1/04:23:32 - +9/01:00:00 -9
SipSipSipSipSipSip - - - ?9/04:00:00
NijeZivotJedanACM -2 +4/04:32:12 +2/01:32:45 +1/04:59:59

output

3

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

Στη χειρότερη περίπτωση οι ήρωές μας θα χάσουν από τις ομάδες ~U~ najgorem će slučaju naš trojac NisamSadaNistaDonio και JeLiMojKockaSeUmio, τερματίζοντας έτσι στην τρίτη θέση.