#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool check(ll a[],ll n,ll mid,ll k){
ll painters=1;
ll minutes=0;
for(int i=0;i<n;i++){
if(minutes+a[i]>mid){
minutes=a[i];
painters++;
if(painters>k){
return false;
}
}
else{
minutes+=a[i];
}
}
return true;
}
void search(ll a[],ll n,ll k){
ll maxi=INT_MIN;
ll sum=0,ans=0;
for(int i=0;i<n;i++){
maxi=max(maxi,a[i]);
sum+=a[i];
ll s=maxi;
ll e=sum;
while(s<=e){
ll mid=(s+e)/2;
if(check(a,n,mid,k)){
ans=mid;
e=mid-1;
}
else{
s=mid+1;
}
}
}
cout<<(ans%10000003)<<endl;
}
int main(){
ll n,k,t;
cin>>n>>k>>t;
ll a[n];
for(int i=0;i<n;i++){
cin>>a[i];
a[i]=a[i]*t;
}
search(a,n,k);
}