#include
#include
using namespace std;
#define ll unsigned long long int
bool valid(ll ar[], ll n, ll k, ll t, ll mid)
{
ll np = 1, total_t = 0;
for(int i=0;i<n;i++)
{
if((total_t + ar[i]*t) < mid)
total_t += ar[i]*t;
else
{
np++;
total_t = ar[i]*t;
if(total_t > mid && (np+1) > k)
return false;
}
}
if(np > k)
return false;
return true;
}
int main()
{
ll ans;
ll n, k, t;
cin>>n>>k>>t;
ll sum = 0;
ll * ar = new ll[n];
for(ll i=0;i<n;i++)
{
cin>>ar[i];
sum += ar[i];
}
sort(ar, ar+n);
ll min_t = t;
ll max_t = sum*t;
while(min_t <= max_t)
{
ll mid = (min_t + max_t)/2;
if(valid(ar, n, k, t, mid))
{
ans = mid%10000003;
// cout<<mid<<endl;
max_t = mid-1;
}
else
{
min_t = mid+1;
// cout<<"false "<<mid<<endl;
}
}
cout<<ans;
return 0;
}