Bridge Crossing

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

Η πρώτη γραμμή της εισόδου περιέχει έναν ακέραιο αριθμό ~M~ ~(1 \le M \le 20)~. Η δεύτερη γραμμή περιέχει το ~Q~ ~(1 \le Q \le 100)~, το μήκος της ουράς που περιμένει να περάσει. Για κάθε άτομο στην ουρά, ακολουθεί ένα ζεύγος γραμμών εισόδου. Το πρώτο από αυτά είναι το όνομα του ατόμου και το δεύτερο είναι ο ατομικός χρόνος αυτού για να περάσει τη γέφυρα. Θυμηθείτε ότι ένας ομαδικός χρόνος διέλευσης θα είναι ο μέγιστος χρόνος διέλευσης για οποιοδήποτε άτομο στην ομάδα.

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

Παράδειγμα

input

2
5
alice
1
bob
5
charlie
5
dobson
3
eric
3

output

Total Time: 9
alice
bob charlie
dobson eric