There are n points on the x-axis (1, 2, 3, ..., n), where the ith point has a cost associated with it denoted by cost[i].

Starting from coordinate x = 0, you can make jumps of length at most k. Whenever you stop at a point, you incur the cost of that point. Find the minimum cost to reach point n by taking jumps of length at most k.

Problem

Input

• n: the number of points on the x-axis
• cost: an array of costs associated with each point
• k: the maximum jump length

Output

• the minimum total cost incurred to reach point n

Example

n = 5 cost = [4, 3, 9, 3, 1] k = 2

The optimal jump pattern is 0 → 2 → 4 → 5. The cost of stopping at points 2, 4, and 5 is 3 + 3 + 1 = 7, which is the minimum possible.

Constraints

• 1 ≤ n ≤ 3 * 10^5
• 1 ≤ k ≤ n
• 1 ≤ cost[i] ≤ 10^9