Vào năm 2027, Trung tâm Điều hành Vệ tinh Quốc gia ghi nhận một chuỗi tín hiệu cảm biến tần số cao được gửi về từ Vệ tinh Không gian số "VNASAT-2027". Dữ liệu nhận được là một dãy gồm ~n~ gói thông tin số nguyên ~A = (a_1, a_2, \dots, a_n)~, biểu thị mức độ nhiễu tín hiệu ở từng mốc thời gian liên tiếp.

Để giải mã được tọa độ chính xác của Vệ tinh, hệ thống máy chủ cần phân chia toàn bộ dãy tín hiệu này thành đúng ~k~ chuỗi con liên tiếp sao cho mỗi chuỗi con chứa ít nhất một gói dữ liệu. Các chuỗi con được đánh số thứ tự từ ~1~ đến ~k~ theo chiều thời gian thu nhận. Hệ thống sẽ thực hiện giải mã tín hiệu bằng cách áp dụng bộ khuếch đại tần số phân tầng: Các gói dữ liệu nằm ở chuỗi con thứ ~j~ ~(1 \le j \le k)~ sẽ được nhân với hệ số khuếch đại đúng bằng ~j~. Tổng năng lượng giải mã thu được từ toàn bộ chuỗi tín hiệu được tính bằng công thức:

~\displaystyle \sum_{i=1}^{n}(a_i \cdot b_i) = a_1 \cdot b_1 + a_2 \cdot b_2 + \dots + a_n \cdot b_n~

Trong đó ~b_i~ là chỉ số của chuỗi con chứa gói dữ liệu thứ ~i~.

Nhiễu tín hiệu có thể có giá trị âm hoặc dương. Do giới hạn về thời gian xử lý thực tế của Vệ tinh trong năm 2027, các kỹ sư lập trình cần tìm một phương án phân chia dãy tín hiệu ~A~ thành ~k~ đoạn liên tiếp sao cho tổng năng lượng giải mã ~S~ đạt giá trị lớn nhất có thể. Ban Tổ chức kỳ thi Học sinh giỏi Tin học năm 2027 yêu cầu bạn lập trình giải quyết bài toán tối ưu hóa nguồn lực không gian số này.

Yêu cầu: Hãy tìm cách chia dãy thành ~k~ đoạn liên tiếp sao cho tổng giá trị hiệu quả thu được là lớn nhất.

Input

• Dòng 1 chứa hai số nguyên dương ~n, k~ ~(1 < k < n \le 10^5)~;

• Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(\forall i: |a_i| \le 10^9)~. Các số trên một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là giá trị cách chia lớn nhất tìm được.

Scoring

Sample Input 1

9 3
-6 5 -7 5 1 -3 -2 3 5

Sample Output 1

18

Notes