Neboderi

Η Domagoj βρίσκεται στη μεγαλούπολη του Λονδίνου! Αυτή τη στιγμή, υπάρχει μια σειρά από ψηλούς ουρανοξύστες μπροστά του και θέλει να βγάλει μια φωτογραφία για να θυμάται τη στιγμή.

Η ακολουθία των ουρανοξυστών μπορεί να αναπαρασταθεί ως μια ακολουθία ~n~ αριθμών ~h_1, h_2, \cdots, h_n~, όπου ο αριθμός ~h_i~ αντιπροσωπεύει το ύψος του ~i~-οστού ουρανοξύστη. Ο Domagoj θα φωτογραφίσει μια συνεχόμενη ακολουθία ουρανοξυστών. Για να καταγράψει περισσότερη από την ομορφιά της πόλης, θέλει να φωτογραφίσει τουλάχιστον ~k~ ουρανοξύστες.

Ο Domagoj έχει μια περίεργη αίσθηση ομορφιάς για μια φωτογραφία. Χαίρεται πολύ όταν στη φωτογραφία υπάρχουν ψηλοί ουρανοξύστες, αλλά ακόμα πιο χαρούμενος όταν τα ύψη τους έχουν μέγιστο κοινό διαιρέτη! Αν ονομάσουμε τα ύψη των συνεχόμενων ουρανοξυστών στη φωτογραφία με ~h_l, \cdots, h_r~ και με ~g~ τον μέγιστο κοινό διαιρέτη των επιλεγμένων υψών, τότε ο Domagoj ορίζει την ομορφιά της φωτογραφίας ως ~g \cdot (h_l + \cdots + h_r)~.

Βοηθήστε τον Domagoj να καθορίσει την ομορφιά της πιο όμορφης φωτογραφίας με τουλάχιστον ~k~ ουρανοξύστες!

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~n~ και ~k~ ~(1 \le k \le n \le 10^6)~, τον αριθμό των ουρανοξυστών και τον αριθμό ~k~.

Η δεύτερη γραμμή περιέχει ~n~ ακέραιους αριθμούς ~h_1, h_2, \cdots, h_n~ ~(1 \le h_i \le 10^6)~, τα ύψη των ουρανοξυστών, κατά σειρά.

Έξοδος

Εκτυπώστε μια γραμμή με τον απαιτούμενο αριθμό του προβλήματος.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	11	~n, k \le 100~
2	22	~n, k \le 5000~
3	27	~h_i \le 100~
4	18	~n, k \le 5 \cdot 10^4~
5	32	Κανένας επιπλέον περιορισμός.

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

input

6 2
2 1 4 4 4 2

output

48

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

Ο Domagoj φωτογράφισε τους ουρανοξύστες ~(4, 4, 4)~, οπότε η συνολική ομορφιά είναι ~4 \cdot (4 + 4 + 4) = 48~.

input

4 1
7 3 9 4

output

81

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

Ο Domagoj φωτογράφισε μόνο τον ουρανοξύστη ~(9)~, οπότε η συνολική ομορφιά είναι ~9 \cdot 9 = 81~.