Chia Dãy

Cho một dãy số nguyên $a_1,a_2,\dots ,a_n$ và một số nguyên $k$.

Bạn cần chia dãy này thành $k$ đoạn con liên tiếp không rỗng. Mỗi phần tử của dãy phải thuộc đúng một đoạn con. Gọi $f(i)$ là chỉ số của đoạn con mà phần tử thứ $i$ thuộc về. Các đoạn con được đánh số từ trái sang phải, từ $1$ đến $k$.

Chi phí của cách chia được định nghĩa bằng:

$$\sum _{i=1}^n(a_i·f(i))$$

Hãy tính chi phí lớn nhất có thể đạt được khi chia dãy $a$ thành $k$ đoạn con liên tiếp không rỗng.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất, là chi phí lớn nhất có thể đạt được.

Ràng buộc

• $1\le k\le n\le 3·{10}^5$
• $|a_i|\le {10}^6$

Ví dụ