Zabava

Άνοιξε μια νέα φοιτητική εστία! Αποτελείται από ~M~ κτίρια, με σήμανση με ακέραιους αριθμούς από ~1~ έως ~M~. Ο κοιτώνας είναι αρχικά άδειος, αλλά σύντομα ~N~ φοιτητές θα μετακομίσουν με ρυθμό ακριβώς ενός μαθητή την ημέρα.

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

Βοηθήστε τη διαχείριση! Γνωρίζοντας σε ποια κτίρια μεταφέρονται οι μαθητές, προσδιορίστε την ελάχιστη δυνατή συνολική στάθμη θορύβου (το άθροισμα των επιπέδων θορύβου όλων των ~N~ μερών) που μπορεί να επιτευχθεί με το άδειασμα ορισμένων κτιρίων το πολύ ~K~ φορές.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N\;(1 \le N \le 1\,000\,000)~, ~M\;(1 \le M \le 100 )~ και ~K\;(1 \le K \le 500)~ από την περιγραφή της εργασίας. Η ~i~-οστή γραμμή, από τις ~N~ συνολικά, περιέχει έναν ακέραιο από το διάστημα ~[1,\;M]~: την ετικέτα των κτιρίων στα οποία μετακομίζει ένας μαθητής την ~i~-οστή ημέρα .

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 40 πόντων, θα ισχύει ~M = 1~.
Σε δοκιμαστικές περιπτώσεις αξίας 60 πόντων, θα κρατήσει ~N \le 1000~ .
Σε δοκιμαστικές περιπτώσεις αξίας 80 πόντων, θα έχει ~N \le 50\,000~ .

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

input

5 1 2
1
1
1
1
1

output

7

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

Το κτίριο εκκενώνεται μετά την πρώτη και την τρίτη μέρα, οπότε τα επίπεδα θορύβου είναι, αντίστοιχα, ~1,\;1,\;2,\;1,\;2~.

input

11 2 3
1
2
1
2
1
2
1
2
1
2
1

output

18

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

Για παράδειγμα, το κτίριο 1 αδειάζει μετά την τέταρτη και όγδοη ημέρα και το κτίριο 2 μετά την έκτη ημέρα. Τα επίπεδα θορύβου είναι, αντίστοιχα, ~1,\;1,\;2,\;2,\;1,\;3,\;2,\;1,\;1,\;2,\;2~.