Gifts from Santa

Christmas comes again in 2021!

Santa, wondering how to hand out gifts, numbered the children and numbered the gifts, then decided to give consecutive gifts as a bundle. A child who does not receive a gift is disappointed, so every child must receive at least one gift.

When handing out gifts, Santa must start with gift 1, bundle several consecutive gifts, then bundle several starting from the gift immediately after, and repeat this. Also, each child can receive only one bundle. However, not all gifts have to be handed out.

For example, with 2 children and 5 gifts, some ways to hand out gifts are [1, 2-3], [1-2, 3-4], [1-3, 4-5], [1-4, 5].

Ways that are not allowed include the following.

• [1-2, 4-5]: It violates the rule that after giving gifts, Santa must continue from the immediately next gift.
• [2-4, 5]: It violates the rule that Santa must start from gift 1.

Each gift has a happiness value that is obtained when it is received. Let $k_i$ be the sum of the happiness values of the gifts received by the $i$-th child.

Santa wants to minimize $\sum_{i=1}^{K} {(k_i - \min_{j=1}^{K}(k_j))}$. Here, $\min_{j=1}^{K}(k_j)$ is the smallest of the sums of happiness values of the gifts received by all children.

Since there are too many gifts to compute this by hand, Santa asks you to write a program that computes this value. Find this value for Santa!

The first line gives an integer $K$, the number of children, and an integer $N$, the number of gifts.

The second line gives $N$ integers $A_i$ (the happiness value of gift $i$), separated by spaces and in order.

• $1 < K \leq 10$
• $K \leq N \leq 202,000$
• $1 \leq A_i < 500,000$ ($1 \leq i \leq N$)
• $\sum_{i=1}^{N}A_i \leq 500,000$

Print the minimum value of $\sum_{i=1}^{K} {(k_i - \min_{j=1}^{K}(k_j))}$.