Ograda

Ο Matija πρέπει να βάψει τον παλιό του φράχτη. Ο φράχτης είναι κατασκευασμένος από ~N~ το πλήθος σανίδες, πλάτους ~1~ εκ. η κάθε μία , και σε ύψος ποικίλλουν. Για να κάνει το βάψιμο εύκολα και γρήγορα, αγόρασε ένα κύλινδρο βαφής, Super Paint Roller Deluxe. Ο κύλινδρος βαφής έχει πλάτος ~X~ εκ.. Το μοντέλο Super Paint Roller Deluxe όμως έχει μια ιδιαιτερότητα. Ο Matija θα πρέπει να αγγίζει πάντα τις σανίδες με όλο το πλάτος του κυλίνδρου, διαφορετικά πέφτει μπογιά γύρω γύρω και λερώνει τα πάντα. Επίσης ο κύλινδρος πρέπει να είναι πάντα παράλληλος με το έδαφος για να αποφευχθεί τυχόν διαρροή. Αυτό σημαίνει ότι προκειμένου ο Matija να χρησιμοποιήσει τον κύλινδρο με ασφάλεια, πρέπει να επιλέξει ~X~ σανίδες και να τις βάψει από κάτω μέχρι την κορυφή της χαμηλότερης σανίδας του φράχτη την οποία μπορεί να φτάσει, με μία κίνηση. Μετά επιλέγει κάποιες άλλες, ~X~ σανίδες, τις βάφει και ούτω καθεξής.
Αυτό αφήνει μέρη ορισμένων σανίδων άβαφα. Ο Matija θα πρέπει να τα καλύψει και αυτά με μπογιά και για να το κάνει έχει μία οδοντόβουρτσα. Αυτό θα είναι προφανώς αρκετά κουραστικό, οπότε σας ζήτησε να τον βοηθήσετε να καλύψει με τον κύλινδρο βαφής, όσο το δυνατόν μεγαλύτερη επιφάνεια. Υπάρχουν περισσότεροι από ένας τρόποι για να το κάνει αυτό, τον ενδιαφέρει συγκεκριμένα αυτός που απαιτεί τον ελάχιστο αριθμό από σαρώσεις.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς, των αριθμό των σανίδων ~N\;(1 \le N \le 1\,000\,000)~ και το πλάτος του κυλίνδρου βαφής ~X\;(1 \le X \le 100\,000)~. Το πλάτος του κυλίνδρου βαφής θα πρέπει να μην υπερβαίνει το πλάτος του φράχτη.
Η δεύτερη γραμμή περιέχει τα ύψη των σανιδών του φράχτη, ~N~ θετικούς ακέραιους, μικρότερους από ~1\,000\,000~.

Έξοδος

Η πρώτη γραμμή θα πρέπει να περιέχει τη μικρότερη δυνατή περιοχή που θα χρειάζεται να βάψει χειροκίνητα ο Matija.
Η δεύτερη γραμμή θα πρέπει να περιέχει τον μικρότερο αριθμό σαρώσεων που χρειάζονται.

Βαθμολογία

Εάν μόνο μία από τις εξόδους είναι σωστή, θα λάβετε το ~50~% των πόντων για αυτό το αρχείο ελέγχου. Πρέπει πάντα να ακολουθείτε κατά γράμμα τη μορφή εξόδου, ακόμα κι αν δεν καταφέρετε να υπολογίσετε και τους δύο αριθμούς. Σε αυτήν την περίπτωση, να εξάγετε οποιονδήποτε ακέραιο στη θέση του αριθμού που δεν υπολογίσατε.

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

input

5 3
5 3 4 4 5

output

3
2

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

Ο Matija χρειάζεται δύο σαρώσεις με τον κύλινδρο του - μία για να βάψει τις σανίδες ~1,\;2~ και ~3~ σε ύψος ~3~ εκ. και μία για να βάψει τις σανίδες ~3,\;4~ και ~5~ σε ύψος ~4~ εκ.. Σημειώστε ότι ~3~ τ.εκ, (~2~ τ.εκ. στη σανίδα ~1~ και ~1~ τ.εκ. στη σανίδα ~5~) μένουν άβαφα. Επίσης, βαμμένα ~3~ τ.εκ. στη σανίδα ~3~ βάφονται από δύο φορές, αλλά δεν πειράζει.

input

10 3
3 3 3 3 3 3 3 3 3 3

output

0
4

input

7 4
1 2 3 4 3 2 1

output

4
4