Đề bài:

Cho mảng A[] gồm N số nguyên không âm và một số nguyên K.

Nhiệm vụ: chia mảng A[] thành hai mảng con:

Một mảng con có kích thước K,

Mảng còn lại có kích thước N-K,

sao cho hiệu giữa tổng hai mảng con là lớn nhất.

Ví dụ:

Với A[] = {8, 4, 5, 2, 10}, K = 2

Ta có thể chia thành {4, 2} và {8, 5, 10}

Hiệu tổng = 23 - 6 = 17, là lớn nhất.

Input

Dòng 1: hai số nguyên N và K (1 ≤ K ≤ N ≤ 10⁵)

Dòng 2: N số nguyên không âm — các phần tử của mảng A[] (0 ≤ A[i] ≤ 10⁹)

Output

Một số nguyên duy nhất: hiệu tổng lớn nhất giữa hai mảng con

Sample Input

5 2
8 4 5 2 10

Sample Output

17