Cho một dãy gồm ~n~ số nguyên không âm. Bạn cần chia dãy thành ~k+1~ đoạn con liên tiếp khác rỗng bằng cách thực hiện thao tác sau đúng ~k~ lần:

1. Chọn một trong các đoạn hiện tại có nhiều hơn một phần tử. Ban đầu chỉ có một đoạn là toàn bộ dãy;

2. Chọn một vị trí giữa hai phần tử liên tiếp của đoạn đó và chia đoạn thành hai đoạn mới khác rỗng.

Sau mỗi lần chia, bạn nhận được số điểm bằng tích của tổng các phần tử trong hai đoạn mới tạo thành.

Yêu cầu: Hãy tìm cách thực hiện ~k~ lần chia để tổng điểm nhận được là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,k~ ~(k+1 \le n \le 3000)~;

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1,a_2,\dots,a_n~ ~(0 \le a_i \le 10^4)~.

Output

Một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Scoring

Sample Input 1

7 3
1 3 4 0 2 3 4

Sample Output 1

108

Notes

Có thể thực hiện các lần chia như sau:

• Chia dãy sau phần tử thứ ~6~, tạo thành ~(1,3,4,0,2,3)~ và ~(4)~, nhận được:

  ~(1+3+4+0+2+3)\cdot 4=52~ điểm;

• Chia đoạn ~(1,3,4,0,2,3)~ sau phần tử thứ ~2~, tạo thành ~(1,3)~ và ~(4,0,2,3)~, nhận được:

  ~(1+3)\cdot(4+0+2+3)=36~ điểm;

• Chia đoạn ~(4,0,2,3)~ thành ~(4,0)~ và ~(2,3)~, nhận được:

  ~(4+0)\cdot(2+3)=20~ điểm.

Tổng điểm là ~52+36+20=108~.