Cho dãy số nguyên \(a_1, 𝑎_2, … , 𝑎_𝑛\) và số nguyên dương \(𝑑\). Hãy tìm cặp chỉ số \((𝑖, 𝑗)\) thỏa mãn điều kiện:

1) \(1 ≤ 𝑖 < 𝑗 ≤ 𝑛\);

2) \(𝑗 − 𝑖 + 1\) chia hết cho \(𝑑\);

3) \(𝑆 = a(i) + a(i+1) +…+a(j)\) đạt giá trị lớn nhất.

Input

• Dòng đầu chứa số nguyên dương \(𝑛\) và \(𝑑 (𝑑 ≤ 𝑛 ≤ 10^6)\);

• Dòng tiếp theo chứa \(𝑛\) số nguyên \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) (các số có giá trị tuyệt đối không vượt quá \(10^9\)).

Output

• Gồm một số là giá trị \(𝑆\) tìm được.

Ràng buộc

• Subtaks 1: 25 % test với \(n ≤ 10^3\)

• Subtaks 2: 75 % test với \(n ≤ 10^6\)

Sample Input

3 2 
1 -2 3

Sample Output

1