#include<bits/stdc++.h>
using namespace std;
bool check(int n,int k,int t,vectorv,int mid){
int curr = 0;
int count = 1;
for(int i=0;i<n;i++){
if(curr+v[i]*t>mid){
count++;
curr = v[i]*t;
if(count>k){
return false;
}
}else{
curr = curr + v[i]*t;
}
}
if(count>k)
return false;
return true;
}
int ans(int n,int k,int t,vectorv){
int ans = -1;
int max_v=v[0];
for(int i=1;i<n;i++)
max_v =max(max_v,v[i]);
int start = max_v*t;
int sum = 0;
for(int i=0;i<n;i++){
sum = sum + v[i];
}
int end = sum*t;
while(start<=end){
int mid = (start + end)/2;
bool check1 = check(n,k,t,v,mid);
if(check1==true){
ans = mid;
end = mid-1;
}else{
start = mid + 1;
}
}
return ans % 10000003;
}
int main() {
int n;
cin>>n;
int k;
cin>>k;
int t;
cin>>t;
vectorv;
for(int i=0;i<n;i++){
int x;
cin>>x;
v.push_back(x);
}
cout << ans(n,k,t,v) << endl;
}
is my logic correct?