Xưởng sản xuất vòng đeo cổ mới sản xuất được một chiếc vòng mới, vòng được xâu bởi N hạt đá, hạt thứ i được sơn màu là một số nguyên Ai (i=1..N). Khách hàng hôm nay thích số nguyên K nên họ yêu cầu xưởng sản xuất điều chỉnh lại màu cho các hạt sao cho bất kỳ K hạt liên tiếp nào trong vòng đều có tổng màu của các hạt bằng nhau. Ví dụ một vòng đạt yêu cầu của khách hàng với K = 3, gồm 8 hạt là: 2 5 8 2 5 8 2 5 8, khi đó các đoạn liên tiếp gồm 3 phần tử của dãy đều có tổng bằng nhau, bằng 15. Chi phí để điều chỉnh màu của một hạt tăng lên hoặc giảm đi 1 đơn vị là 1 đồng.

Yêu cầu: Giúp xưởng sản xuất điều chỉnh lại màu của chuỗi vòng thỏa mãn yêu cầu của khách hàng với chi phí ít nhất.

Dữ liệu: gồm:

• Dòng đầu chứa 2 số nguyên dương N và K (K ≤ N ≤ 10^5).
• Dòng thứ hai chứa N số nguyên dương A1, A2,...,AN; (|Ai| ≤ 10^9. với mọi i = 1..N).

Kết quả: Ghi ra một số nguyên là chi phí ít nhất tìm được.

Ví dụ:

VONGHAT.INP

9 3
1 4 7 2 5 8 3 6 9

VONGHAT.OUT

6

Ràng buộc:

• Có 25% số test tương ứng với 25% số điểm có |Ai| ≤ 100.
• 75% số test, tương ứng với 75% số điểm còn lại không có ràng buộc gì thêm.

Nguồn