#include
#include
using namespace std;
typedef long long ll;
ll painters( ll a[], ll n, ll totMaxLen){
ll i = 0, ptrs = 1, len =0;
while( i++<n ){
len += a[i];
if( len > totMaxLen){
len = a[i];
ptrs++;
}
}
return ptrs;
}
int main() {
ll a[1000000],n,t,k, sum =0 , maxi=0;
cin>>n>>k>>t;
for ( ll i =0; i< n; i++){
cin>>a[i];
maxi = max( maxi, a[i]);
sum+= a[i];
}
sort( a, a+n);
ll i = maxi, j = sum, ans;
while( i<=j){
ll mid = (i+j)/2;
ll ptrs = painters( a,n,mid);
if(ptrs <= k){
j = mid-1;
ans = mid;
}
else{
i = mid+1;
}
}
ll len=0, tim = 0;
for( ll k = 0; k<n; k++){
if( len+a[k]> ans){
tim = max(tim, lent);
len =0;
}
len+= a[k];
}
tim = max(tim, lent);
cout<<tim%10000003<<endl;
return 0;
}