Phần thưởng

Alice vừa đoạt giải quán quân trong một kỳ thi lập trình danh giá. Ban tổ chức trao thưởng thông qua một trò chơi như sau. Có $n$ thẻ xếp trên một hàng dài, trên mỗi thẻ viết một số nguyên dương. Ban tổ chức cho phép Alice thực hiện nhiều bước để chọn ra đúng $k$ cặp thẻ, mỗi bước thực hiện theo một trong các quy tắc sau:

• Chọn $2$ thẻ đầu hàng;
• Chọn $2$ thẻ cuối hàng;
• Chọn $1$ thẻ đầu hàng và $1$ thẻ cuối hàng;
• Loại $1$ thẻ đầu hàng ra khỏi hàng;
• Loại $1$ thẻ cuối hàng ra khỏi hàng.

Sau mỗi bước nếu chọn được $2$ thẻ thì loại $2$ thẻ đó ra khỏi hàng và Alice nhận được số tiền thưởng bằng giá trị tuyệt đối của hiệu hai số ghi trên hai thẻ đó.

Yêu cầu: Hãy giúp Alice tìm cách chơi chọn đúng $k$ cặp thẻ để đạt được tổng số tiền thưởng là lớn nhất.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương $n$ và $k$ $(2\times k\le n)$;
• Dòng thứ hai chứa $n$ số nguyên dương là giá trị ghi trên từng thẻ, mỗi thẻ một số tương ứng lần lượt từ đầu hàng. Các số có giá trị không vượt quá ${10}^9$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng tiền thưởng lớn nhất tìm được.

Ràng buộc

• $2\times k\le n\le 300$;
• Giá trị trên mỗi thẻ là số nguyên dương không vượt quá ${10}^9$.

Subtasks

• Subtask 1 ($40\%$ số test, $40\%$ số điểm): $n\le 300$, $k\le 2$;
• Subtask 2 ($40\%$ số test, $40\%$ số điểm): $n\le 30$, $2\times k=n$;
• Subtask 3 ($20\%$ số test, $20\%$ số điểm): $n\le 300$.

Ví dụ