Cho dãy số nguyên \(A = (a_1, a_2, ..., a_n)\). Với hai số nguyên dương \(l, r(1 \leq l \leq r \leq n)\), gọi trọng số của cặp \((l, r)\) là tổng giá trị của các phần tử liên tiếp từ \(l\) đến \(r\) của dãy \(A\).

Yêu cầu: Cho dãy A và số nguyên k, hãy chọn ra k cặp \((l_1, r_1), (l_2, r_2), ..., (l_k, r_k)\) thõa mãn:

• \(1 \leq l_i \leq r_i \leq n\)
• Các cặp này đôi một khác nhau
• \(X \leq r_i - l_i + 1\)
• Tổng trọng số của \(k\) cặp đã chọn là lớn nhất

Input

• Dòng đầu chứa ba số nguyên dương \(n, k, X\)
• Dòng thứ hai chứa n số nguyên \(a_i (|a_i| \leq 10^5)\)

Output

• Ghi ra một số nguyên duy nhất là tổng trọng số lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100; k \leq 1000\)
• Subtask \(2\) (\(15\%\) số điểm): \(n \leq 1000; k \leq 10^5\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^4; k \leq 10^4\)
• Subtask \(4\) (\(20\%\) số điểm): \(n, k \leq 5 \cdot 10^4\)
• Subtask \(5\) (\(20\%\) số điểm): \(n, k \leq 3 \cdot 10^5\)
• Subtask \(6\) (\(15\%\) số điểm): \(n \leq 3 \cdot 10^5; k \leq 10^7\).

Example

4 4 2
3 2 -6 8 

18