Akcija

Χριστούγεννα, καιρός για δώρα. Ο κ. Malnar έχει ανάγκη από ιδέες για δώρα. Αν και βαθιά απορροφημένος στις σκέψεις του, το τηλεοπτικό πρόγραμμα του τραβά την προσοχή: "Ειδική προσφορά! Αυτό το καταπληκτικό προϊόν διατίθεται προς πώληση μόνο με ~w~ kunas (κροάτικο νόμισμα). Καλέστε τώρα γιατί η προσφορά είναι διαθέσιμη μόνο αν καλέσετε μέσα στα επόμενα ~d~ λεπτά. Αλλά δεν είναι μόνο αυτό~\ldots~".

Υπάρχουν ~n~ διαφορετικά προϊόντα προς πώληση, όπου το ~i~-οστό προϊόν έχει κόστος ~w_i~ και είναι διαθέσιμο για παραγγελία μέχρι και το λεπτό ~d_i~. Η πραγματοποίηση κλήσης για την παραγγελία απαιτεί ένα λεπτό. Ένα υποσύνολο προϊόντων ονομάζεται αποκτήσιμο εάν είναι δυνατό να δημιουργηθεί μια ακολουθία των κλήσεων που παραγγέλνουν αυτά τα προϊόντα τηρώντας τις αναφερόμενες προθεσμίες. Κανένα προϊόν δεν μπορεί να παραγγελθεί περισσότερες από μία φορές.

Ο κ. Malnar σκοπεύει να αγοράσει όσο το δυνατόν περισσότερα προϊόντα, στην ελάχιστη δυνατή τιμή, αλλά δεν είναι ακόμα σίγουρος για το ποια προϊόντα πρέπει να αγοράσει. Συγκρίνει δύο υποσύνολα προϊόντων που μπορούν να αποκτηθούν με τον ακόλουθο τρόπο: το καλύτερο αποκτήσιμο υποσύνολο είναι αυτό με τα περισσότερα προϊόντα και, εάν έχουν ίσο μέγεθος, είναι αυτό που έχει και το μικρότερο συνολικό κόστος (άθροισμα κόστους επιλεγμένων προϊόντων).

Ο κ. Malnar θα ταξινομήσει τα αποκτήσιμα υποσύνολα με τον τρόπο που περιγράφεται και θα λάβει υπόψη του ~k~ από τα καλύτερα. Γράψτε ένα πρόγραμμα που καθορίζει το μέγεθος και το συνολικό κόστος για ~k~ από τα καλύτερα διαθέσιμα υποσύνολα προϊόντων.

Είσοδος

Η πρώτη γραμμή περιέχει θετικούς ακέραιους αριθμούς ~n~ και ~k~, τον αριθμό των διαφορετικών προϊόντων και τον αριθμό των υποσυνόλων που μπορούν να ληφθούν υπόψη, αντίστοιχα. Το ~k~ θα είναι μικρότερο ή ίσο του αριθμού των υποσυνόλων που μπορείτε να αποκτήσετε.

Οι ακόλουθες ~n~ γραμμές περιέχουν δύο θετικούς ακέραιους ~w_i\;(1 \le w_i \le 10^9)~ και ~d_i\;(1 \le d_i \le n)~, το κόστος του ~i~-οστού προϊόντος και το τελευταίο λεπτό για το οποίο ισχύουν οι προσφορές, αντίστοιχα.

Έξοδος

Στην ~i~-οστή γραμμή εκτυπώστε το μέγεθος και το συνολικό κόστος του ~i~-οστού καλύτερου αποκτήσιμου υποσυνόλου.

Βαθμολογία

Σε κάθε υποπρόβλημα ισχύει ότι ~1 \le n, k \le 2000~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~k = 1,\;w_i = \ldots = w_n~
2	20	~k = 1~
3	20	~k = 2~
4	10	~1 \le n \le 20~
5	30	~1 \le n, k \le 100~
6	20	Κανένας επιπλέον περιορισμός.

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

input

3 1
1 1
1 1
1 3

output

2 2

input

4 3
1 1
10 1
2 3
10 3

output

3 13
3 22
2 3

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

Τα προϊόντα 1 και 2 δεν μπορούν να βρίσκονται ταυτόχρονα σε ένα αποκτήσιμο υποσύνολο, επομένως τα τρία καλύτερα υποσύνολα με δυνατότητα απόκτησης είναι τα ~\{1,\;3,\;4\}, \;\{2,\;3,\;4\}~ και ~\{1,\;3\}~.

input

2 4
1 1
2 2

output

2 3
1 1
1 2
0 0