Traktor

Ο Mirko πήρε ένα υπέροχο νέο τρακτέρ για τα Χριστούγεννα που μπορεί να μαζέψει ακόμα και μανιτάρια! Τα μανιτάρια αναπτύσσονται σε ένα λιβάδι τετράγωνου σχήματος που μπορεί να τοποθετηθεί σε επίπεδο συντεταγμένων έτσι ώστε η κάτω αριστερή άκρη του να βρίσκεται στο ~(1,\;1)~ και η πάνω δεξιά άκρη στο ~(10^5,\;10^5)~.

Αρχικά, δεν υπάρχουν μανιτάρια στο λιβάδι, αλλά συνολικά το ~N~ θα αναπτυχθεί με τρόπο που κάθε δευτερόλεπτο να φυτρώνει ακριβώς ένα νέο μανιτάρι σε έναν κενό χώρο στο λιβάδι.

Ο οικονομικός Mirko θέλει να οδηγήσει το τρακτέρ του μόνο μία φορά και να μαζέψει τουλάχιστον ~K~ μανιτάρια. Η διαδρομή του ξεκινά σε ένα από τα σημεία του λιβαδιού και μπορεί να κινηθεί μόνο σε κατευθύνσεις παράλληλες προς τις πλευρές ή τις διαγώνιες του. Το τρακτέρ του Mirko είναι εξαιρετικά γρήγορο και διανύει μεγάλες αποστάσεις σε αμελητέο χρόνο. Λόγω της τεράστιας ταχύτητας, ο Mirko δεν μπορεί να κάνει στροφές κατά τη διάρκεια της διαδρομής.

Βοηθήστε τον Mirko και καθορίστε τον ελάχιστο αριθμό δευτερολέπτων μετά τα οποία μπορεί να διαλέξει τον επιθυμητό αριθμό μανιταριών.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους ~N\;(2 \leq N \leq 10^6)~ και ~K\;(2 \leq K \leq N)~, τον αριθμό των μανιταριών που θα αναπτυχθούν και τον αριθμό των μανιταριών που θέλει να μαζέψει ο Mirko.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς ~X_i~ και ~Y_i\;(1 \leq X_i ,\;Y_i \leq 10^5)~, τις συντεταγμένες του ~i~-οστού μανιταριού που αναπτύσσεται σε αυτό το λιβάδι.

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~50~% των συνολικών πόντων, θα έχει ~1 \leq X_i,\;Y_i \leq 300~.

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

input

4 3
1 2
3 4
3 2
4 5

output

4

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

Ο Mirko ξεκινά την διαδρομή του στο σημείο ~(1,\;2)~ και κινείται προς το μανιτάρι που βρίσκεται στο ~(4,\;5)~.

input

7 4
3 1
2 2
4 1
3 2
2 3
1 4
1 3

output

6

input

5 2
1 1
2 1
1 2
1 3
1 4

output

2