Cho dãy n số nguyên A₁, A₂,..., A_n và một số nguyên K.

Bạn được phép thực hiện K lần thao tác. Mỗi thao tác chọn một phần tử trong dãy và thay thế nó bằng số đối của chính nó (tức là thay A[i] bằng -A[i]).

Hãy tính tổng lớn nhất có thể đạt được của dãy sau khi thực hiện tối đa K lần thao tác.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên n và k.
• Dòng thứ hai chứa n số nguyên A₁, A₂, ..., A_n.

Dữ liệu ra

Một số nguyên duy nhất là tổng lớn nhất có thể đạt được sau khi thực hiện K thao tác.</p> lưu ý: số thao tác tối thiểu là 1 và tối đa là k

Ví dụ

Input

5 4
-3 0 5 -1 2

Output

11

Ta được phép thực hiện 4 lần đổi dấu để tối đa hóa tổng của dãy.

• Bước 1: Đổi dấu -3 thành 3 → dãy: 3 0 5 -1 2
• Bước 2: Đổi dấu -1 thành 1 → dãy: 3 0 5 1 2
• Không cần đổi thêm nữa vì các phần tử còn lại đều không âm.

Tổng của dãy: 3 + 0 + 5 + 1 + 2 = 11.

Input

4 3
9 7 8 5

Output

19

Giới hạn

• 1 ≤ n ≤ 100
• -10⁹ ≤ A_i ≤ 10⁹