Cho dãy ~a~ gồm ~n~ số nguyên dương. Bạn được chọn đúng ~k~ cặp số bằng các thao tác, mỗi thao tác có thể chọn một trong các cách sau:

• 1) Chọn ~2~ số đầu hàng.

• 2) Chọn ~2~ số cuối hàng.

• 3) Chọn ~1~ số đầu hàng và ~1~ số cuối hàng.

• 4) Loại ~1~ số đầu hàng ra khỏi hàng.

• 5) Loại ~1~ số cuối hàng ra khỏi hàng.

Sau mỗi thao tác, nếu bạn chọn thao tác ~1~, ~2~, ~3~ thì sẽ được cộng thêm số điểm bằng giá trị tuyệt đối của ~2~ số bạn chọn, đồng thời loại ~2~ số đó ra khỏi hàng và được tính là chọn 1 cặp số. Ngược lại với thao tác ~4~ và ~5~, bạn không được tính là chọn một cặp số.

Hãy tìm cách thực hiện đúng ~k~ thao tác để đem về số điểm là cao nhất. Biết ban đầu bạn có số điểm bằng 0.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~ ~(2*k \le n)~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a_i \le 10^9)~

Ouput

• In ra một số nguyên duy nhất là số điểm lớn nhất có thể thu về sau khi thực hiện đúng ~k~ thao tác.

Subtask

• Có 40% test thỏa mãn điều kiện: ~n \le 300~, ~k \le 2~.
• Có 40% test thỏa mãn điều kiện: ~n \le 30, 2*k = n~.
• Có 20% test thỏa mãn điều kiện: ~n \le 300~

Sample Test

Input

6 2
1 3 10 2 1 4

Output

12

Giải thích:

• Thao tác ~1~: Chọn ~2~ thẻ cuối hàng và được cộng ~|4-1| = 3~ điểm.
• Thao tác ~2~: Loại thẻ ở cuối hàng có giá trị bằng ~2~.
• Thao tác ~3~: Chọn một thẻ ở đầu hàng và một thẻ ở cuối hàng, thu được thêm ~|10-1| = 9~ điểm.
• Tổng cộng sẽ được ~2~ cặp số tương ứng ~12~ điểm.