bool possible(int x,vector<int>&a,int k){
int usedWorkers=1;
int currentWorkersWorkload=0;
int n=a.size();
for(int i=0;i<n;i++){
if(a[i]>x) return false;
if(a[i]+currentWorkersWorkload<=x){
currentWorkersWorkload+=a[i];
}
else {
usedWorkers++;
currentWorkersWorkload=a[i];
}
}
if(usedWorkers<=k)return true;
else return false;

}
void solve(){ // binary search on answer
vector<int> arr={10,20,30,40,50,60,70,80,90}; // could be unsorted
int n=arr.size();
int k=3;
int left=0;
int right=1e6;//sum of all elements
int ans=1e6;
while(left<=right){
int mid=(left+right)/2;
if(possible(mid,arr,k)){
ans=mid;
right=mid-1;
}
else left=mid+1;
}
cout<<ans<<endl;
}