Thông tin

Trong sứ mệnh khám phá bản đồ số, một rô-bốt tự hành được giao nhiệm vụ di chuyển dọc theo một dãy gồm \(N\) điểm thu thập thông tin, được đánh số từ \(1\) đến \(N\).

Tại mỗi điểm \(i\), nếu rô-bốt thu thập thông tin thì sẽ thu được lượng dữ liệu \(A_i\).

Rô-bốt được lập trình để chỉ quét các điểm thông tin liên tiếp, và phải tuân thủ điều kiện:

• Số lượng điểm thu thập phải là bội số của \(K\).

Yêu cầu: Hãy tìm một đoạn liên tiếp gồm đúng \(L\) điểm (\(L\) là bội số của \(K\)) sao cho tổng lượng dữ liệu thu được là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên \(N\), \(K\) (\(1 \le K \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9\)).

Output

• In ra một số nguyên: tổng lượng dữ liệu lớn nhất có thể thu được từ một đoạn liên tiếp có độ dài chia hết cho \(K\).

Scoring

• Subtask 1 (25%): \(N \le 1000\).
• Subtask 2 (25%): \(K = 1\).
• Subtask 3 (50%): Không có ràng buộc gì thêm.

Input

5 2
1 2 3 4 5

Output

14

Notes

Các đoạn liên tiếp có độ dài chia hết cho \(K = 2\) gồm:

• \((1,2)\): tổng = 3

• \((2,3)\): tổng = 5

• \((3,4)\): tổng = 7

• \((4,5)\): tổng = 9

• \((1,4)\): tổng = 10

• \((2,5)\): tổng = 14

Đoạn \((2,5)\) là tối ưu.