Shelf leveling

Find the cheapest stretch of shelves to bring to one common stock level.

A store has a row of shelves. The string stock has one digit character per shelf, in order, and each digit ("0" to "9") is the number of units on that shelf. A stock clerk will choose k consecutive shelves and bring all k of them to the same stock level. She can choose any whole-number level she likes for the stretch, and the level can be anything, even if no shelf holds that many units right now.

Changing a shelf costs money per unit:

• adding one unit to a shelf costs add,
• removing one unit from a shelf costs cut.

(Units are bought or discarded, not moved between shelves.) Shelves that are already at the chosen level cost nothing. For a given stretch, the clerk picks the level that makes the total cost smallest.

Input: stock, the string of shelf stocks, the stretch length k, and the unit prices add and cut.

Output: a list [start, cost]: start is the index of the first shelf of the cheapest stretch and cost is its total cost. If several stretches have the same lowest cost, use the one with the smallest start.

The row of shelves can be very long and k can be large, so re-examining each stretch from scratch will be too slow.