Studentsko

Το ερχόμενο Σάββατο πραγματοποιείται ο ετήσιος ομαδικός μαθητικός διαγωνισμός στο πινγκ-πονγκ φοιτητών που έχουν εγγραφεί στο Πανεπιστήμιο του Zagreb! Κάθε ομάδα αποτελείται από ~K~ μαθητές. Οι ενθουσιασμένοι μαθητές, ~N~ από αυτούς, περιμένουν στην ουρά για να εγγραφούν.

Ο Krešo εργάζεται στο γραφείο εγγραφής. Δεν θέλει πραγματικά να κάνει τη δουλειά του και έτσι αποφάσισε να μην επιτρέψει στους μαθητές να επιλέξουν ομάδα. Αποφάσισε ότι η πρώτη ομάδα θα αποτελείται από τους πρώτους ~K~ μαθητές που θα στέκονται στην ουρά, η δεύτερη ομάδα από τους ακόλουθους ~K~ μαθητές, η τρίτη από τους ακόλουθους ~K~ μαθητές και ούτω καθεξής... (Το ~N~ θα διαιρείται με το ~K~, ώστε να μην μείνει κανείς κρεμασμένος.)

Ο Ante έχει υπολογίσει την ικανότητα κάθε παίκτη με έναν ακέραιο αριθμό. Θα ήθελε να έχει τους ~K~ πιο δυνατούς παίκτες στην πρώτη ομάδα, τους παρακάτω ~K~ πιο δυνατούς στη δεύτερη ομάδα κ.ο.κ.

Ο Krešo μόλις έφυγε για το διάλειμμά του και ο Ante αποφασίζει να μετατοπίσει τους μαθητές που στέκονται στην ουρά για να πετύχει τον στόχο του. Ο τρόπος με τον οποίο τα μετατοπίζει είναι ότι λέει σε έναν μαθητή να βγει από την ουρά και να επιστρέψει στην ουρά μετά από έναν άλλο μαθητή ή να πάει στο μπροστινό μέρος της ουράς. Του παίρνει ένα λεπτό για να το κάνει αυτό.

Είναι πιθανό ο Krešo να επιστρέψει από το διάλειμμά του οποιαδήποτε στιγμή, οπότε ο Ante πρέπει να πετύχει τον στόχο του το συντομότερο δυνατό. Βοηθήστε τον Άντε να καθορίσει τον ελάχιστο αριθμό λεπτών που είναι απαραίτητος για να πετύχει τον στόχο του.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους ~N~ και ~K\;(1 \leq K \leq N \leq 5\,000)~. Ο ακέραιος ~N~ θα διαιρεθεί με το ~K~.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~v_i\;(1 \leq v_i \leq 10^9 )~ χωρισμένους με διάστημα, ο ~i~-οστός αριθμός δηλώνει την ικανότητα του ~i~-οστού παίκτη που στέκεται στην ουρά.

Όλοι οι διαγωνιζόμενοι θα έχουν διαφορετικά επίπεδα δεξιοτήτων.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον ελάχιστο απαιτούμενο αριθμό λεπτών.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30% των συνολικών πόντων, θα έχει ~N \leq 20~.

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

input

4 1
9 12 5 13

output

1

input

6 2
16 2 1 7 5 10

output

1

input

6 3
7 9 8 3 6 5

output

3

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

Ο Ante θα πρέπει να μετακινήσει τους μαθητές με τα επίπεδα δεξιοτήτων 5, 6 και 3 στο μπροστινό μέρος της ουράς. Του παίρνει τρία λεπτά για να το κάνει.