You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by a[i]. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum. You can only choose consecutive toffee packets to put in a box.

N,M <= 10^5. a[i] <= 10^3. Time Limit : 1s.

Input : 4 2 10 3 5 7

Output: 13

Explanation : Below are the possible assignments of toffee packets to boxes. 10 [3 5 7] 10 3 [5 7] 10 3 5 [7] For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13.

Can anyone can explain me the logic or data structure , algo behind it to solve it ?

Thanks In Advance.