Namje Adventure

A sinkhole opened in the middle of Namjegwan. The 1333 family measured its depth from the time a stone took to hit the bottom, and they now want to explore it. They borrow a rope that Jooheon kept for a hobby and start climbing down.

Figure 1. A descent that is allowed (left) and a descent that is not allowed (right).

With a rope of length $L$, a person can move down by any distance from $1$ to $L$. Moving down by $i$ costs $x_i$ energy. The rope is too short for safe joint descent, so only the highest person moves each time. A person cannot move into a depth that another person occupies.

Depth is the distance from the hole entrance. At the start, the $N$ people hang at depths $1, 2, \dots, N$, one per depth. At the bottom, the $N$ people must occupy depths $D-N+1, D-N+2, \dots, D$, one per depth. It does not matter who stands where.

Find the minimum total energy spent until everyone reaches the bottom.

The first line contains $N$, $D$ and $L$. The second line contains $x_1, x_2, \dots, x_L$ separated by spaces.

All values are integers with $1 \le N \le 3$, $5 \le L \le 12$, $2N \le D \le 10^{10}$ and $1 \le x_i \le 1000$ for every $i$.

Print the minimum total energy spent until the family reaches the bottom.

Figure 1 shows the movement rule. A descent is allowed when the destination depth is empty, and it is blocked when another person occupies it.

The figure below shows two arrivals. The left side uses the minimum energy and the right side arrives with more energy.