BubbleCutting
Given an integer m and an integer sequence a of length n, you have to split the given sequence into consecutive subsequences. The sum of elements in any subsequence must be less than or equal to m. Let M be the sum of maximal elements of the subsequences. Your task is to find the split that minimizes M.
Figure 1. One possible cutting for the given example bellow
InputThe first line contains two positive integers n and m (1≤n≤100 000 and 1≤m≤1.000.000.000), where n is the number of elements in the given sequence and m is the maximal allowed sum of elements in a subsequence. The following line contains n integers – elements of the sequence. All elements are in the range [0, 1.000.000].
OutputThe output consists of one integer: “-1” (without quotes) if a solution does not exist; Otherwise, the minimal sum of maximal elements for any split (M).
Input:
7 14
1 1 1 6 2 6 14
Output:
21
Submit solution
Sign in to submit a solution.