DHEXP - Biểu thức

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Một dãy gồm n số nguyên không âm a 1 , a 2 ,..., a n được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả ( n­ -1) khoảng trắng. Người ta muốn đặt k dấu cộng và ( n- 1- k ) dấu trừ vào ( n­ -1) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1+69 là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm n số nguyên không âm a 1 , a 2 ,..., a n và số nguyên dương k , hãy tìm cách đặt k dấu cộng và ( n- 1- k ) dấu trừ vào ( n­ -1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

  • Dòng đầu chứa hai số nguyên dương n, k ( k < n );
  • Dòng thứ hai chứa n số nguyên không âm a 1 , a 2 ,..., a n ( a n ≤ 10 6 )

Output

Một số nguyên là giá trị của biểu thức đạt được.

Example

Input:
5 2
28 9 5 1 69
Output:
100

Ghi chú:

  • Có 50% số test ứng với 50% số điểm có n ≤ 10 5 và k = 1;
  • Có 50% số test còn lại ứng với 50% số điểm có n ≤ 10 5;

  • Người up: voj