Tourism

Σχεδιάζετε ένα ταξίδι για να επισκεφθείτε ~N~ τουριστικά αξιοθέατα. Τα αξιοθέατα αριθμούνται από το ~1~ έως το ~N~ και πρέπει να τα επισκεφθείτε με αυτή τη σειρά. Μπορείτε να επισκεφθείτε το πολύ ~K~ αξιοθέατα ανά ημέρα και θέλετε να προγραμματίσετε το ταξίδι σας ώστε να διαρκέσει όσο το δυνατόν λιγότερες ημέρες.

Υπό αυτούς τους περιορισμούς, θέλετε να βρείτε ένα πρόγραμμα που να έχει μια ωραία ισορροπία μεταξύ των αξιοθέατων που επισκέπτεστε κάθε μέρα. Για να είμαστε ακριβείς, αναθέτουμε μια βαθμολογία ~a_{i}~ στο αξιοθέατο ~i~. Δεδομένου ενός προγράμματος, σε κάθε ημέρα αποδίδεται μια βαθμολογία ίση με τη μέγιστη βαθμολογία όλων των αξιοθέατων που επισκεφθήκατε εκείνη την ημέρα. Τέλος, οι βαθμολογίες της κάθε ημέρας αθροίζονται για να προκύψει η συνολική βαθμολογία του προγράμματος. Ποια είναι η μέγιστη δυνατή συνολική βαθμολογία του προγράμματός σας, με τις λιγότερες δυνατές ημέρες;

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο ακέραιους αριθμούς ~N~ και ~K\;(1 \le K \le N \le 10^{6})~.

Η επόμενη γραμμή θα περιέχει ~N~ ακέραιους αριθμούς ~a_{i}\;(1 \le a_{i} \le 10^{9})~ χωρισμένους με κενά διαστήματα.

Για ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~2K \ge N~ .

Για επιπλέον ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~K \le 100~ και ~N \le 10^{5}~.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό, τη μέγιστη δυνατή συνολική βαθμολογία.

Παράδειγμα

input

5 3
2 5 7 1 4

output

12

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

Θα πρέπει να έχουμε τουλάχιστον δύο ημέρες για να επισκεφθούμε όλα τα αξιοθέατα, αφού δεν μπορούμε να επισκεφθούμε όλα τα αξιοθέατα σε μία ημέρα.

Η επίσκεψη των δύο πρώτων αξιοθέατων την 1η ημέρα θα δώσει βαθμολογία ~5~, ενώ η επίσκεψη των τριών τελευταίων αξιοθέατων την ημέρα ~2~ θα δώσει βαθμολογία ~7~, και έτσι η συνολική βαθμολογία θα είναι ~12~.

Η επίσκεψη τριών αξιοθέατων την 1η ημέρα και δύο αξιοθέατων την 2η ημέρα, που είναι η μόνη εναλλακτική για επισκέψεις σε όσο το δυνατόν λιγότερες ημέρες, θα έδινε συνολική βαθμολογία ~7 + 4 = 11~.