DCANDY2

Submit solution
Points: 35
Time limit: 1.0s
Memory limit: 512M
Problem type

Có \(n\) gói kẹo được đánh số từ 1 đến \(n\), gói kẹo thứ \(i\) có \(a_i\) viên. Cần chọn ra \(2*k\) gói kẹo chia cho hai em nhỏ, mỗi em nhận \(k\) gói kẹo liên tiếp nhau, hai em không được nhận chung 1 gói kẹo. Gọi tổng số kẹo em thứ nhất nhận là \(T_1\), em thứ hai nhận là \(T_2\).

Yêu cầu: Tìm cách chia kẹo cho hai em sao cho \(T_1-T_2\) đạt giá trị lớn nhất.

Input

  • Dòng thứ nhất chứa số nguyên \(n,k (2≤n≤10^6,1≤k≤n/2)..\)

  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤10^9 ).\)

Output

  • Ghi ra giá trị \(T_1-T_2\) lớn nhất tìm được.

Ràng buộc

  • Subtask 1: 60% số điểm với \(n≤100\).

  • Subtask 2: 20% số điểm với \(n≤10^3. \)

  • Subtask 3: 23% số điểm với \(n≤10^6.\)

Sample Input

5 2
6 5 1 2 10

Sample Output

8

Comments