English statement is here

Vào một ngày nọ, một thí sinh là Dinde tham gia một cuộc thi gây quỹ từ thiện để ủng hộ những con người có hoàn cảnh khó khăn. Ban tổ chức đã giao cho Dinde một thử thách khá khó nhằn: BTC đã giao do Dinde một dãy ~N~ tấm thẻ có các giá trị là ~A_i~ ~(1 \le i \le N, |A_i| \le 10^9)~, Dinde sẽ phải sử dụng hết ~K~ lần lật thẻ, với một lần lật thẻ, giá trị trên thẻ đó sẽ trở thành số đối của chính nó. Ví dụ: nếu thẻ có giá trị là ~2~, sau khi được lật thì thẻ sẽ mang giá trị là ~-2~. Nếu giá trị của thẻ là ~0~ thì giá trị sau khi lật của thẻ vẫn là ~0~.

Dinde được yêu cầu hãy tìm ra tổng giá trị lớn nhất của các thẻ sau ~K~ lần lật thẻ. Hãy tìm giúp Dinde tìm tổng giá trị lớn nhất của các thẻ đó là bao nhiêu nhé!

Lưu ý: Một thẻ có thể lật nhiều lần tuỳ ý.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~N, K~ ~(1 \le K \le N \le 2 \times 10^5)~.
• Dòng thứ hai chứa dãy số nguyên ~A_1, A_2, A_3, ..., A_N~ ~(|A_i| \le 10^9)~.

Dữ liệu ra

Một dòng duy nhất chứa một số nguyên là kết quả bài toán.

Ràng buộc

• Subtask ~1~ ~(20\%)~: ~N \le 20~.
• Subtask ~2~ ~(20\%)~: ~N \le 10^4~
• Subtask ~3~ ~(30\%)~: ~N \le 2 \times 10^5, |A_i| \le 10^4~.
• Subtask ~4~ ~(30\%)~: Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

5 2
3 -4 2 -3 -1

Dữ liệu ra

11

Giải thích

Dinde phải lật thẻ ~2~ lần và Dinde lựa chọn lật ~2~ thẻ là thẻ thứ ~2~ và thẻ thứ ~4~.

Tổng giá trị của các thẻ là: ~3 + 4 + 2 + 3 - 1 = 11~.