Chọn dấu


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.