#include <bits/stdc++.h>
using namespace std;
bool CanAllocated(int A[],int N,int M,int mid){
int cnt=1,res=0;
for(int i=0;i<N;i++){
if(A[i]>mid) return false;
res+=A[i];
if(res>mid){
cnt++;
res=A[i];
}
if(cnt>M) return false;
}
return true;
}
//Function to find minimum number of pages.
int findPages(int A[], int N, int M)
{
//code here
// sort(A,A+N);
if(N<M) return -1;
int low=A[0],high=0,ans=-1;
for(int i=0;i<N;i++){
high+=A[i];
low=min(low,A[i]);
}
while(low<=high){
int mid=(low+high)/2;
if(CanAllocated(A,N,M,mid)){
ans=mid;
high=mid-1;
}
else low=mid+1;
}
return ans;
}
int main() {
int n = 4, m = 2;
int A[] = {12,34,67,90};
cout<<findPages(A,n,m);
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKYm9vbCBDYW5BbGxvY2F0ZWQoaW50IEFbXSxpbnQgTixpbnQgTSxpbnQgbWlkKXsKICAgICAgICBpbnQgY250PTEscmVzPTA7CiAgICAgICAgZm9yKGludCBpPTA7aTxOO2krKyl7CiAgICAgICAgICAgIGlmKEFbaV0+bWlkKSByZXR1cm4gZmFsc2U7CiAgICAgICAgICAgIHJlcys9QVtpXTsKICAgICAgICAgICAgaWYocmVzPm1pZCl7CiAgICAgICAgICAgICAgICBjbnQrKzsKICAgICAgICAgICAgICAgIHJlcz1BW2ldOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKGNudD5NKSByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIHJldHVybiB0cnVlOwp9CiAgICAvL0Z1bmN0aW9uIHRvIGZpbmQgbWluaW11bSBudW1iZXIgb2YgcGFnZXMuCmludCBmaW5kUGFnZXMoaW50IEFbXSwgaW50IE4sIGludCBNKSAKICAgIHsKICAgICAgICAvL2NvZGUgaGVyZQogICAgICAgIC8vIHNvcnQoQSxBK04pOwogICAgICAgIGlmKE48TSkgcmV0dXJuIC0xOwogICAgICAgIGludCBsb3c9QVswXSxoaWdoPTAsYW5zPS0xOwogICAgICAgIGZvcihpbnQgaT0wO2k8TjtpKyspewogICAgICAgICAgICBoaWdoKz1BW2ldOwogICAgICAgICAgICBsb3c9bWluKGxvdyxBW2ldKTsKICAgICAgICB9CiAgICAgICAgd2hpbGUobG93PD1oaWdoKXsKICAgICAgICAgICAgaW50IG1pZD0obG93K2hpZ2gpLzI7CiAgICAgICAgICAgIGlmKENhbkFsbG9jYXRlZChBLE4sTSxtaWQpKXsKICAgICAgICAgICAgICAgIGFucz1taWQ7CiAgICAgICAgICAgICAgICBoaWdoPW1pZC0xOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgbG93PW1pZCsxOwogICAgICAgIH0KICAgICAgICByZXR1cm4gYW5zOwogICAgfQppbnQgbWFpbigpIHsKICAgIGludCBuID0gNCwgbSA9IDI7CglpbnQgQVtdID0gezEyLDM0LDY3LDkwfTsKICAgIGNvdXQ8PGZpbmRQYWdlcyhBLG4sbSk7CiAgICAKfQ==