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.|

DHEXP - Biểu thức

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/dhexp


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;

Được gửi lên bởi:VOJ Team
Ngày:2015-04-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Duyen hai 2015 khoi 10

hide comments
2015-05-04 05:23:35 BRAIN
Chú ý phần tử đầu tiên luôn mang dấu cộng :| nếu sort thì chỉ qsort từ 2 -> n rồi tham lam
2015-05-03 16:28:49 Thắng Ðam Mê
1 đấm AC, sort cái là ra :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.