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.
Image: cutting
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
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.