You are traveling along a straight road of length l, starting at position $0$ and ending at position l. Along the road, there are n road signs located at coordinates given by the array position, where position[0] = 0 and position[n - 1] = l. Each sign $i$ indicates the travel time per unit distance, given by time[i], required to traverse the road segment starting from position[i] to the next sign position[i + 1].

You are allowed to perform at most k merge operations on adjacent inner signs (signs that are neither at position $0$ nor at position l). In a single merge operation, you can choose an inner sign at index i ($1 \leq i < m - 1$, where m is the current number of signs), remove it, and add its time[i] value to the next sign at index i + 1 (so the new time for the sign at index i + 1 becomes time[i] + time[i + 1]).

The total travel time is the sum of (position[j + 1] - position[j]) * time[j] across all remaining segments from $j = 0$ to $m - 2$.

Return the minimum total travel time possible after performing at most k merge operations.

Constraints:

• $1 \leq$ l $\leq 10^5$

• $2 \leq$ n $\leq \min($l $+ 1, 50)$

• $0 \leq$ k $\leq \min($n $- 2, 10)$

• position.length $==$ n

• position[0] $= 0$ and position[n - 1] $==$ l

• position is sorted in strictly increasing order.

• time.length $==$ n

• $1 \leq$ time[i] $\leq 100$

• $1 \leq \sum$ time $\leq 100$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.