Phân đoạn dãy số

Bạn được tham gia một trò chơi với dãy gồm $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$. Trong trò chơi này, bạn phải chia dãy đã cho thành $k+1$ đoạn con liên tiếp khác rỗng. Để thu được $k+1$ đoạn, bạn lặp lại các bước sau đúng $k$ lần:

1. Chọn một đoạn tùy ý có nhiều hơn một phần tử (ban đầu chỉ có một đoạn, đó chính là toàn bộ dãy).
2. Chọn một vị trí nào đó giữa hai phần tử liên tiếp của đoạn đã chọn để chia nó thành hai đoạn mới khác rỗng.

Mỗi lần thực hiện xong hai bước này, bạn nhận được số điểm bằng tích của tổng các số trong đoạn mới thứ nhất và tổng các số trong đoạn mới thứ hai.

Yêu cầu: Hãy tìm cách chơi để tổng điểm nhận được sau $k$ lần chia là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $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)$.

Dữ liệu ra

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

Ràng buộc

• $1\le k$, $k+1\le n\le 3000$.
• $0\le a_i\le {10}^4$.
• $70\%$ số test có $n\le 300$.

Ví dụ