Hokej

Η ημερομηνία ενός μεγάλου τουρνουά μαραθωνίου χόκεϊ επί πάγου πλησιάζει. Όπως συμβαίνει συχνά στο μαραθώνιο χόκεϊ επί πάγου, το παιχνίδι διαρκεί ~M~ λεπτά. Στο γήπεδο (πάγος) βρίσκονται, όπως στο κανονικό χόκεϊ επί πάγου, σε κάθε δεδομένη στιγμή, έξι παίκτες από κάθε ομάδα. Ωστόσο, ένας αγώνας μαραθώνιου χόκεϊ επί πάγου μπορεί να διαρκέσει πολύ ώρα, έτσι οι προπονητές έφεραν ένα σωρό παίκτες σε λεωφορεία και αεροπλάνα, ώστε να μπορούν να κάνουν αντικαταστάσεις όταν οι παίκτες κουράζονται.

Ένας από τους προπονητές είναι ο ήρωας της ιστορίας μας και το όνομά του είναι Ante. Ο Ante έφερε \(Ν\) παίκτες στο τουρνουά. Για κάθε παίκτη, γνωρίζει δύο πράγματα: την ποιότητα του παίκτη - ~K~, και την αντοχή του παίκτη - ~I~. Η αντοχή του παίκτη είναι ο συνολικός χρόνος σε λεπτά που μπορεί να περάσει ένας παίζοντας στο παιχνίδι χωρίς να κουραστεί. Εάν ο παίκτης έπαιξε για ~X~ λεπτά, μετά ξεκουράστηκε στον πάγκο και μετά έπαιξε ξανά για ~Y~ λεπτά, ο συνολικός χρόνος παιχνιδιού του είναι ~X + Y~. Όταν ένας παίκτης παίζει συνολικά λεπτά ίσα με την αντοχή του, κουράζεται και δεν μπορεί να συνεχίσει να παίζει, οπότε εκείνη τη στιγμή κάποιος πρέπει να τον αντικαταστήσει, διαφορετικά θα λιποθυμήσει στον πάγο και θα καταλήξει στο νοσοκομείο (ο μαραθώνιος χόκεϊ επί πάγου είναι ένα επικίνδυνο παιχνίδι).

Η ποιότητα της ομάδας σε ένα δεδομένο λεπτό του παιχνιδιού είναι το άθροισμα της ποιότητας των παικτών αυτής της ομάδας που παίζουν αυτήν τη στιγμή. Ο Ante δεν είναι σπουδαίος προπονητής, γι' αυτό σου ζήτησε να βρεις τους αρχικούς έξι παίκτες και το πρόγραμμα των αναπληρωματικών, ώστε να μπορέσει να πετύχει το μέγιστο δυνατό άθροισμα της ποιότητας της ομάδας για όλα τα λεπτά του αγώνα - ~Z~. Είναι εγγυημένο ότι θα είναι πάντα δυνατό να δημιουργηθεί ένα πρόγραμμα τέτοιο ώστε να υπάρχουν έξι παίκτες στο παιχνίδι σε κάθε λεπτό. Για παράδειγμα, αν το παιχνίδι διήρκησε για 3 λεπτά, και αν στο πρώτο λεπτό η ποιότητα της ομάδας ήταν 15, στο δεύτερο 12, ​και στο το τρίτο 14, το ~Z~ θα είναι ίσο με ~15 + 12 + 14 = 41~.

Σημείωση: στο μαραθώνιο χόκεϊ επί πάγου, δεν υπάρχει τερματοφύλακας, γιατί το παιχνίδι πρέπει να είναι ενδιαφέρον!

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους θετικούς ακέραιους αριθμούς ~M~ και ​~N\;(1 \le M \le 500\,000,\;6 \le N \le 500\,000)~,​ τη διάρκεια του παιχνιδιού στο λεπτά, και τον αριθμό των παικτών που έφερε ο Ante.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο θετικούς ακέραιους ανά παίκτη, ~K\;(1 \le K \le 100\,000)~ και ~I\;(1 \le I \le M)~, η ποιότητα και η αντοχή.
Οι παίκτες αριθμούνται από το 1 έως το ~N~, με τη σειρά που δίνεται στην εισαγωγή (ο αριθμός του πρώτου παίκτη είναι 1, ο δεύτερος είναι 2, κτλ).

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει το μέγιστο δυνατό ~Z~.
Η δεύτερη γραμμή εξόδου πρέπει να περιέχει ακριβώς έξι αριθμούς - τους αριθμούς των έξι παικτών που ξεκινούν το παιχνίδι.
Η τρίτη γραμμή εξόδου πρέπει να περιέχει τον αριθμό των αντικαταστάσεων ~B~, που δεν πρέπει να υπερβαίνει τα 3 ∗ N.
Κάθε μία από τις ακόλουθες ~B~ γραμμές πρέπει να περιέχει, με σειρά από την πρώτη έως την πιο πρόσφατη αντικατάσταση, τις πληροφορίες για τους αναπληρωτές, τρεις αριθμούς ανά αναπληρωματικό, ~X\;(1 \le X < M)~, ~A~ και ~B~ , όπου ~X~ είναι ο αριθμός των λεπτών από την έναρξη του παιχνιδιού όταν γίνεται η αλλαγή, ~A~ είναι ο αριθμός του παίκτη που βγαίνει από το παιχνίδι και πηγαίνει στον πάγκο και ~B~ είναι ο αριθμός του παίκτη που μπαίνει στο παιχνίδι ως αντικαταστάτης του.
Επιτρέπονται πολλές αλλαγές στο ίδιο λεπτό, αλλά ένας παίκτης δεν μπορεί να μπει στο παιχνίδι, και μετά να φύγει την ίδια στιγμή, ή το αντίστροφο.
Εάν υπάρχουν πολλές λύσεις, τυπώστε οποιαδήποτε.

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

input

200 6
3 200
4 200
5 200
6 200
7 200
8 200

output

6600
1 2 3 4 5 6
0

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

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

input

9 9
10 3
9 3
13 9
5 3
15 9
100 9
3 6
2 6
1 6

output

1260
1 2 3 4 5 6
3
3 1 7
3 2 8
3 4 9

input

3 9
100 3
100 3
100 3
100 3
100 2
100 1
50 1
30 2
1 1

output

1610
1 2 3 4 5 6
2
1 6 8
2 5 7