Đan mới tạo ra một trò chơi trên một vòng tròn số như sau: Ban đầu máy tính sẽ tạo ngẫu nhiên \(n\) số nguyên \(a_{0}, a_{1}, \ldots, a_{n - 1}\) và xếp lần lượt từng số lên vòng tròn theo chiều kim đồng hồ (xem ví dụ dưới đây cho vòng tròn 8 số).

Người chơi sẽ vào vai là một chú thỏ và thực hiện các hành động:

Ban đầu chú thỏ sẽ chọn một vị trí \(s\ (0 \leq s < n)\) để xuất phát.

Sau đó, chú thỏ sẽ thực hiện \(k\) lần nhảy \(123\) bắt đầu từ \(s\) theo chiều kim đồng hồ trên vòng tròn. Các vị trí tương ứng với bước nhảy \(1, 3\) chú thỏ sẽ được cộng điểm là số tại vị trí đó, các vị trí tương ứng với bước nhảy \(2\) chú thỏ bị trừ điểm là số tương ứng tại vị trí đó. Chú thỏ cần tìm cách nhảy để đạt được nhiều điểm nhất.

Ví dụ, trong hình trên, với \(s = 1\) và \(k = 2\), ba số được tô màu đỏ \((a_{1}, a_{3}, a_{4})\) tương ứng với lần nhảy \(123\) thứ nhất, ba số được tô màu xanh \((a_{5}, a_{7}, a_{0})\) tương ứng lần nhảy thứ hai.

Tổng điểm chú thỏ nhận được là: \((a_{1} - a_{3} + a_{4}) + (a_{5} - a_{7} + a_{0})\).

Một cách hình thức: Nếu tạo dãy gồm \(n\) số bắt đầu từ phần tử thứ \(s\) theo chiều kim đồng hồ ta nhận được dãy \(b_{0}, b_{1}, \ldots, b_{n - 1}\), trong đó \(b_{0} = a_{s}, b_{1} = a_{(s + 1) \% n}, \ldots, b_{n - 1} = a_{(s + n - 1) \% n}\). Khi đó, cần tìm các chỉ số \(0 \leq x_{1} < y_{1} < z_{1} < x_{2} < y_{2} < z_{2} < \ldots < x_{k} < y_{k} < z_{k} \leq n - 1\) để tổng: \((b_{x_{1}} - b_{y_{1}} + b_{z_{1}}) + (b_{x_{2}} - b_{y_{2}} + b_{z_{2}}) + \ldots + (b_{x_{k}} - b_{y_{k}} + b_{z_{k}})\) đạt giá trị lớn nhất.

Yêu cầu: Cho vòng tròn số và số nguyên dương \(k\), tính điểm lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k\) \((3 \times k \leq n)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{0}, a_{1}, \ldots, a_{n - 1}\) \((|a_{i}| \leq 10^{9}\) với \(0 \leq i \leq n - 1)\).

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị tổng điểm lớn nhất đạt được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20, k = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 2000, k = 1\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 200\).
• Subtask \(5\) (\(20\%\) số điểm): \(n \leq 2000\).

Example

8 2
1 1 0 -1 1 1 0 -1

6