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

1. Chọn một đoạn tuỳ ý với nhiều hơn một phần tử (đầu tiên bạn chỉ có một đoạn - đó chính là dãy ban đầu).

2. Chọn một vị trí nào đó giữa hai phần tử của đoạn đã chọn để chia nó ra làm 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 một điểm số bằng tích của hai tổng các số trong hai đoạn mới chia ra. Yêu cầu: Với cách chơi như trên, bạn hãy tìm cách chơi để đạt được tổng điểm lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ với ~k+1≤n ≤3000~;

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ với ~0 ≤ a_i ≤ 10^4, 1 ≤ i ≤ n~ là các phần tử của dãy số.

Output

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

Sample input

7 3
1 3 4 0 2 3 4

Sample output

108

Giải thích

Trong ví dụ bạn có thể giành được 108 điểm theo cách sau:

• Đầu tiên bạn có dãy số (1, 3, 4, 0, 2, 3, 4) gồm 1 đoạn. Bạn chia dãy ra thành hai đoạn sử dụng điểm chia sau phần tử thứ sáu và nhận được: ~(1 + 3 + 4 + 0 + 2 + 3) × 4 = 52~ điểm.
• Bạn đang có hai đoạn (1, 3, 4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ hai và nhận được: ~(1 + 3) × (4 + 0 + 2 + 3) = 36~ điểm.
• Bạn đang có ba đoạn (1, 3), (4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ tư và nhận được: ~(4 + 0) × (2 + 3) = 20~ điểm.

Như vậy, sau 3 bước thực hiện nói trên bạn chia dãy số thành 4 đoạn (1, 3), (4, 0), (2, 3), (4) và nhận được: ~52 + 36 + 20 = 108~ điểm.

Subtasks

• Có 70% số test tương ứng với 70% số điểm của bài có ~n ≤ 300;~
• Có 30% số test còn lại tương ứng với 30% số điểm của bài có ~n ≤ 3000.~