Cho dãy số nguyên 𝑎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.

Sample Input

3 2 
1 -2 3

Sample Output

1