MKSEQ

Submit solution
Points: 100
Time limit: 1.0s
Memory limit: 493M
Problem type

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.

Sample Input

3 2 
1 -2 3

Sample Output

1

Comments