Chọn dấu
Cho dãy số nguyên $N$ phần tử $a_1,a_2,...,a_N$. Với mỗi số nguyên, hãy chọn dấu cộng hoặc trừ ở trước nó, sao cho tổng các phần tử sau khi chọn dấu là nhỏ nhất.
Tuy nhiên để tăng độ khó, ta cần chọn đúng $K$ phần tử được đặt dấu cộng và $N-K$ đặt dấu trừ.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N,K \ (1\le K\le N\le 10^5)$;
- Dòng thứ hai chứa $N$ số nguyên $a_i \ (|a_i| \le 10^4)$.
Kết quả
- Giá trị tổng nhỏ nhất tìm được.
Chấm điểm
40; $N\le 20$. 30; $N\le 10^3$. 30; Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
6 3
1 9 -3 4 5 6
output
-18
Giải thích
Chọn dấu cộng cho 3 số 1, -3, 4 được: $1 + (-3) + 4 - 9 -5 -6=-18$.
Comments