Lottery

Jessica đang dư rất nhiều tiền và muốn mua xổ số.

Loại xổ số mà cô ta mua rất đặc biệt, có thể biểu diễn dưới dạng một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Mỗi tờ vé số là một dãy con từ \(l\) tới \(r\) (\(1 \le l \le r \le n\)) của dãy xổ số ban đầu \(a_l, a_{l+1}, \ldots, a_r\) và được kí hiệu là \((l, r)\).

Một cách mua \(x\) tờ vé số \((l_1, r_1), (l_2, r_2), \ldots, (l_x, r_x)\) được gọi là hợp lệ khi:

• Với \(1 \le i \le x-1\) thì \(r_i < l_{i+1}\) và \(a_{r_i} + 1 = a_{l_{i+1}}\).

• Với \(1 \le i \le x\) thì \(a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}\) tạo thành một dãy các số tự nhiên liên tiếp. (Ví dụ: \([1,2,3]\), \([6,7,8,9,10]\), \([5]\))

Nói cách khác, các tờ vé số là các dãy con liên tiếp không cắt nhau của dãy \(a\) sao cho khi ghép các tờ vé số lại với nhau theo thứ tự từ trái qua phải thì tạo thành một dãy các số tự nhiên liên tiếp.

Tổng giá trị phần thưởng của cách mua sẽ là tổng tất cả các số trên những tờ vé số, tức là \(\sum_{i=1}^{x} \sum_{j=l_i}^{r_i} a_j\).

Yêu cầu: Jessica chỉ có thể mua không quá \(k\) tờ vé số, hãy giúp cô ấy tìm được cách mua có tổng giá trị phần thưởng lớn nhất và cho biết giá trị đó là bao nhiêu.

Input

• Dòng thứ nhất gồm \(2\) số nguyên dương \(n\) và \(k\) (\(3 \le n \le 2 \times 10^5\), \(1 \le k \le 100\));

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

Ràng buộc:

• Subtask 1: Có \(20\%\) số test tương ứng với \(20\%\) số điểm với \(n \le 20\);

• Subtask 2: Có \(20\%\) số test tương ứng với \(20\%\) số điểm với \(k = 1\);

• Subtask 3: Có \(20\%\) số test tương ứng với \(20\%\) số điểm với \(k = 2\) và \(n \le 6900\);

• Subtask 4: Có \(20\%\) số test tương ứng với \(20\%\) số điểm với \(k = 2\);

• Subtask 5: Có \(10\%\) số test tương ứng với \(10\%\) số điểm với \(3 \le k \le 10\);

• Subtask 6: Có \(10\%\) số test tương ứng với \(10\%\) số điểm còn lại không có ràng buộc gì thêm.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Example 1

Input:

6 2
1 2 3 5 4 6

Output:

11

Example 2

Input:

8 2
2 3 4 2 4 5 5 6

Output:

20

Example 3

Input:

12 3
2 3 4 1 4 5 8 1 3 4 5 6

Output:

20

Note

Ở test ví dụ đầu tiên, cách chọn tối ưu là \((4,4)\), \((6,6)\): hai tờ vé chứa các số \(5\) và \(6\) liên tiếp nhau, tổng \(11\).

Ở test ví dụ thứ hai, cách chọn tối ưu là \((1,3)\), \((7,8)\): ghép lại được \(2,3,4,5,6\), tổng \(20\).

Ở test ví dụ thứ ba, cách chọn tối ưu là \((1,1)\), \((9,12)\): ghép lại được \(2,3,4,5,6\), tổng \(20\).