Cho số nguyên dương \(n, d\) và dãy số nguyên \(a_1,a_2, …, a_n. \)

Yêu cầu: Tìm cặp chỉ số \((i,j)\) thỏa mãn điều kiện:

• \(1≤ i < j ≤ n;\)

• \(j – i + 1\) chia hết cho d;

• \(S= a_i + a_{i+1} + ... + a_j\) đạt giá trị lớn nhất.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(d (1 ≤ n,d ≤ 10^6);\)

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

Output

• Gồm một dòng chứa một số nguyên \(S\) lớn nhất tìm được.

Ràng buộc

• Subtask 1: 70% test với \(n ≤ 2000.\)

• Subtask 2: 30% test với \(n ≤ 10^6.\)

Sample Input

10 4
1 2 -4 5 2 4 2 2 1 -6

Sample Output

14