Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

DHEXP - Biểu thức

no tags 

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274811/problem/M

Một dãy gồm n số nguyên không âm a1, a2,..., an đượ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ả (-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 (-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 a1, a2,..., an 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 (-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 a1, a2,..., an (an ≤ 106)

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 ≤ 105k = 1;
  • Có 50% số test còn lại ứng với 50% số điểm có n ≤ 105;

Added by:VOJ Team
Date:2015-04-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Duyen hai 2015 khoi 10