Maximum Sum of Valid Subarray

Given an array of integers representing the heights of boxes arranged in a row, an integer \(K\) specifying the length of a subarray, and an integer \(D\) representing the maximum allowed absolute difference between any two consecutive boxes, your task is to find the maximum sum of any contiguous subarray of length exactly \(K\) that satisfies the following condition:

For every consecutive pair \(a_i\) and \(a_{i+1}\) in the subarray, it must hold that \(|a_{i+1} - a_i| \le D\).

If no such subarray exists, output -1.

Input is provided via standard input (stdin) and the result should be output to standard output (stdout).

inputFormat

The input consists of four lines:

1. The first line contains an integer (N) — the number of boxes.
2. The second line contains an integer (K) — the required subarray length.
3. The third line contains (N) space-separated integers representing the heights of the boxes.
4. The fourth line contains an integer (D) — the maximum allowed absolute difference between two consecutive boxes.

outputFormat

Output a single integer — the maximum sum of any valid subarray of length (K). If no such subarray exists, output -1.## sample

6
3
1 2 3 4 5 6
1

15