Kisik

Η Αποικιακή Συμμαχία Διαγαλαξιακών Εθνών (Colonial Alliance of Intergalactic Nations - CAIN) αποφάσισε να χτίσει μια πόλη στον Άρη για ~K~ οικογένειες. Ως εκ τούτου, είναι απαραίτητο να κατασκευαστούν συνολικά ~K~ κτίρια, ένα για κάθε οικογένεια. Για κάθε οικογένεια, θα επιλεγεί ένα από τα ~N~ διαφορετικά σχέδια κτιρίων που εκπονήθηκαν από τους καλύτερους αρχιτέκτονες του σύμπαντος. Όλα τα κτίρια έχουν ορθογώνιο σχήμα και το i-oστό κτίριο έχει πλάτος ~W_i~ μονάδες και ύψος ~H_i~ μονάδες. Επιπλέον, λόγω της διαφορετικότητας την οποία προωθεί η CAIN, όλες οι οικογένειες θα έχουν διαφορετικά σχέδια.

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

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

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~N~ και ~K~ από την περιγραφή της εργασίας ~(1 \le K \le N \le 1\;000\;000)~.
Στις επόμενες ~N~ γραμμές υπάρχουν δύο ακέραιοι αριθμοί ~W_i~ και ~H_i~, που αποτελούν το πλάτος και το ύψος του i-οστού κτιρίου ~(1 \le W_i, H_i \le 1\;000\;000)~. Όλα τα ζεύγη ~(W_i~, ~H_i)~θα είναι διαφορετικά.

Έξοδος

Γράψτε την ελάχιστη ποσότητα αέρα στην πρώτη γραμμή.

Βαθμολογία

Στα υποπροβλήματα συνολικής αξίας 40 βαθμών ισχύει ότι το Ν θα είναι μικρότερο ή ίσο του ~1\;000~.

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

input

4 3
2 3
2 2
1 4
3 2

output

20

input

3 3
1 1
3 3
2 2

output

18

input

4 1
6 4
4 5
19 1
3 6

output

18