Minimizing Candy Distribution Weight Difference

Blue wants to distribute (n) packets of candies among (m) children on his birthday. The packets are numbered from (1) to (n) and the (i)th packet has weight (w_i). Every packet must be given away. Each child must receive at least one packet, and the packets given to a child must form a contiguous block (by their numbering).

To help achieve a fair distribution – i.e. so that the difference between the maximum total weight and the minimum total weight among the children is as small as possible – Blue is allowed to buy additional copies of some candy packets. However, if a packet is duplicated, then any child can receive at most one copy of that packet. In other words, each candy packet (identified by its number) may appear in the distribution at most twice.

A valid distribution is defined by assigning to each child an interval (I_i=[L_i,R_i]) of packet indices such that (I_1, I_2, \dots ,I_m) satisfy

1. (L_1=1,\quad R_m=n,)
2. The union (I_1 \cup I_2 \cup \cdots \cup I_m = [1,n]) (i.e. every packet is given to at least one child),
3. Each child’s block is contiguous,
4. For any packet (j), it is contained in at most two intervals (so if an interval is shared between two consecutive children, that packet is used twice).

Notice that if two consecutive children have overlapping intervals, the overlapping packets are considered to be purchased additionally (i.e. duplicated) and count in both children’s sums.

The objective is to choose the intervals (and hence decide at which boundaries to duplicate a packet) so that the difference between the maximum total weight and the minimum total weight among all children is minimized. Output this minimum difference.

For example, consider (n=5) with weights (6, 1, 2, 7, 9):

• If (m=2), one optimal strategy is to duplicate every packet and assign each child the full interval ([1,5]). Then each child gets total weight (25) and the difference is (0).

• If (m=3), one solution is to duplicate packet (3) only and assign the intervals as follows: child1 gets packets (1)–(3) (total (9)); child2 gets packets (3)–(4) (total (9)); child3 gets packet (5) (total (9)). The difference is (0).

• If (m=5), one optimal strategy is to duplicate packets (4) and (5) so that one valid assignment is:

• Child1: packets (1)–(2) (sum = (7)),
• Child2: packets (3)–(4) (sum = (9)),
• Child3: packet (4) (sum = (7)),
• Child4: packet (5) (sum = (9)),
• Child5: packet (5) (sum = (9)). The difference in this case is (9-7=2).

Your task is to compute the minimum possible difference between the maximum and minimum total weights a child can get under a valid distribution strategy.

inputFormat

The first line contains two integers (n) and (m) (the number of candy packets and the number of children, respectively).
The second line contains (n) integers (w_1, w_2, \dots, w_n) representing the weights of the candy packets.

outputFormat

Output a single integer representing the minimum possible difference between the maximum total weight and the minimum total weight among all children in any valid distribution.

sample

5 2
6 1 2 7 9

0