Minimum Coins for Jumping Robot Upgrade

This problem is based on the traditional game of hopscotch, also known as "跳飞机" in Chinese, where a player jumps from one cell to another on a line of cells with each cell containing a score. In this game, there are n cells arranged in a line to the right of a starting position, and each cell i (1-indexed) has an integer score a[i].

A robot is designed to play this game. Initially, the robot is flawed as it can only jump a fixed distance of d cells at a time. However, by spending g coins, its flexibility increases by g. The improved robot can choose its jump distance as follows:

• If g < d, in each move it may jump any distance in the range \(d-g, d-g+1, \ldots, d+g\).
• If g \ge d, in each move it may jump any distance in the range \(1, 2, 3, \ldots, d+g\).

The robot starts at position 0 (to the left of cell 1). In each move, it must jump to a cell that is to the right of its current position. When the robot lands on a cell, it collects the score written on that cell. The game can be stopped at any time, and the total score is the sum of the scores from all visited cells.

The objective is to achieve a total score of at least k. Your task is to determine the minimum number of coins g the robot owner must spend in order to achieve a score of at least k by choosing an optimal sequence of jumps.

Note: Each jump must land on a valid cell (i.e. within the range 1 to n).

inputFormat

The first line contains three integers n, d, and k — the number of cells, the original fixed jump distance and the required minimum score respectively.

The second line contains n integers \(a[1], a[2], \ldots, a[n]\) representing the scores of the cells from left to right.

outputFormat

Output a single integer representing the minimum number of coins g required to modify the robot so that it can achieve a score of at least k.

sample

5 3 7
1 2 3 4 5

2