Bài 10.5. Cặp Vị Trí Năng Lượng Tối Ưu - [Độ khó: Khó]

Trong cuộc thám hiểm Sao Hỏa, robot của bạn được giao nhiệm vụ thu thập mẫu khoáng vật dọc theo một con đường thẳng tắp. Mỗi vị trí trên con đường có một "giá trị năng lượng" nhất định. Robot của bạn có một bộ cảm biến đặc biệt chỉ có thể hoạt động hiệu quả khi hai vị trí mẫu được chọn không quá xa nhau. Cụ thể, nếu robot chọn vị trí \(i\) và vị trí \(j\) (với \(i < j\)), thì khoảng cách giữa chúng (\(j - i\)) không được vượt quá một giới hạn \(K\). Bạn cần giúp robot tìm ra hai vị trí thỏa mãn điều kiện khoảng cách, và có tổng giá trị năng lượng (\(A[i] + A[j]\)) là lớn nhất có thể.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương \(N\) (\(2 \le N \le 2 \cdot 10^5\)) và \(K\) (\(1 \le K < N\)), lần lượt là tổng số vị trí và khoảng cách tối đa cho phép. Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)), là giá trị năng lượng tại vị trí thứ \(i\). Các số cách nhau bởi một dấu cách.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng giá trị năng lượng lớn nhất tìm được.

Ví dụ:

Input:

7 3
10 2 8 5 12 3 7

Output:

20

Giải thích:

• \(N = 7\), \(K = 3\). Mảng năng lượng \(A = [10, 2, 8, 5, 12, 3, 7]\).
• Chúng ta cần tìm \(A[i] + A[j]\) lớn nhất sao cho \(i < j\) và \(j - i \le 3\).
• Xét các cặp \((i, j)\) và tổng \(A[i] + A[j]\):
  • Nếu \(j=1\) (vị trí 2, \(A[1]=2\)): Không có \(i < 1\).
  • Nếu \(j=2\) (vị trí 3, \(A[2]=8\)):
    • \(i=0\) (\(A[0]=10\)): \(j-i = 2 \le 3\). Tổng \(10+8=18\).
    • \(i=1\) (\(A[1]=2\)): \(j-i = 1 \le 3\). Tổng \(2+8=10\).
  • Nếu \(j=3\) (vị trí 4, \(A[3]=5\)):
    • \(i=0\) (\(A[0]=10\)): \(j-i = 3 \le 3\). Tổng \(10+5=15\).
    • \(i=1\) (\(A[1]=2\)): \(j-i = 2 \le 3\). Tổng \(2+5=7\).
    • \(i=2\) (\(A[2]=8\)): \(j-i = 1 \le 3\). Tổng \(8+5=13\).
  • Nếu \(j=4\) (vị trí 5, \(A[4]=12\)):
    • \(i=1\) (\(A[1]=2\)): \(j-i = 3 \le 3\). Tổng \(2+12=14\).
    • \(i=2\) (\(A[2]=8\)): \(j-i = 2 \le 3\). Tổng \(8+12=20\).
    • \(i=3\) (\(A[3]=5\)): \(j-i = 1 \le 3\). Tổng \(5+12=17\).
  • ... và tiếp tục cho đến \(j=N-1\).
• Tổng lớn nhất tìm được là \(8 + 12 = 20\) (với \(i=2, j=4\), khoảng cách \(4-2=2 \le 3\)).