The board cuts

Problem

Don Filiberto runs the carpentry shop on the corner and charges for a cut by the length of the piece he puts through the saw: splitting a board of 10 centimeters costs 10, no matter where he splits it. A board arrives with the customer's marks and he has to cut it at every one of them, but he picks the order, and that is where the saving is: after the first cut he is left with two shorter pieces, and every cut after that is paid on the piece it falls in.

Write a function that takes length, a whole number from 1 up (the centimeters the board measures), and marks, a list of distinct whole numbers from 1 to length minus 1: how many centimeters from the left edge each cut goes. The marks come in any order and the list may be empty. Return a whole number: the least it can cost him to make all the cuts.

With a board of 10 and marks at 2, 4 and 7, the cheapest way costs 20. Cutting at 4 first costs 10 and leaves the pieces from 0 to 4 and from 4 to 10; the cut at 2 now falls in a piece of 4 and the cut at 7 in one of 6, so the bill is 10 plus 4 plus 6. Starting at 2 comes out more expensive: 10, then 8 for the cut at 4 and 6 for the cut at 7, which is 24.

With a single mark there is nothing to choose: the only cut costs length. If there are no marks, there is nothing to cut and the answer is 0.

There are boards with up to 20 marks.

Examples

• The example

  10, [2, 4, 7] → 20

• Cutting at the edge first costs more

  20, [1, 9, 10, 11, 19] → 51

• A single mark

  8, [3] → 8

• The marks come out of order

  10, [7, 2, 4] → 20

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def cut_cost(length, marks):
    pass

function cutCost(length, marks) {
}