Cheapest prep schedule: hints, no solution

A prep line has a row of tasks, and performing task i costs costs[i]. Tasks may be skipped, but skipping too many in a row stalls the line: in the final schedule there must never be more than k consecutive skipped tasks, counting any skipped tasks before the first performed task and after the last performed task too. Choose which tasks to perform so that this holds and the total cost is as small as possible, and return that cost. If the row has at most k tasks you may perform none, for a cost of 0. Your solution must run in time linear in the number of tasks, so trying every earlier choice for every task will be too slow.

Examples

Input

costs = [4, 2, 7, 1, 9], k = 1

Output

3

Note

Perform the tasks costing 2 and 1. The skipped tasks are never adjacent, and one is skipped at each end.

Input

costs = [3, 5, 2], k = 0

Output

10

Note

With no skips allowed, every task is performed.

Input

costs = [6, 6, 6], k = 3

Output

0

Constraints

• 0 <= costs.length <= 300000
• 0 <= costs[i] <= 9
• 0 <= k <= 300000

Hint 1: a nudge

Think about the last task you perform among the first few. Which earlier performed tasks are allowed to come right before it?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing