You are given a $0$ indexed integer array prices, where prices[i] represents the price of purchasing the $(i + 1)^{ ext{th}}$ fruit.

The market provides an offer: if you purchase the $(i + 1)^{ ext{th}}$ fruit for prices[i] coins, you are allowed to claim the next $i + 1$ fruits for free. Subsequent fruits from index $i + 1$ up to index $2 \cdot i + 1$ can be taken at no cost.

Return the minimum number of coins needed to acquire all the fruits.

Note: You can choose to purchase a fruit even if you are eligible to take it for free, in order to activate its promotional reward.

Constraints:

• $1 \leq$ prices.length $\leq 1000$

• $1 \leq$ prices[i] $\leq 10^5$

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.