/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
using namespace std;
bool can_paint(int boards[],int n,int k,int t,int mid)
{
int cnt=1;
int time=0;
for(int i=0;i<n;i++)
{
time+=(boards[i]*t);
time=time%10000003;
if(time > mid)
{
cnt++;
time=boards[i]*t;
time=time%10000003;
}
}
if(cnt > k )
return false;
else
{
return true;
}
}
int main() {
int n,k,t;
cin>>n>>k>>t;
int boards[n];
int s=0,e=0;
for(int i=0;i<n;i++)
{
cin>>boards[i];
s=max(s,boards[i]);
e+=boards[i];
}
s*=t;
s=s%10000003;
e*=t;
e=e%10000003;
int ans=0;
while(s<=e)
{
int mid=((s+e)%10000003)/2;
if(can_paint(boards,n,k,t,mid))
{
ans=mid;
e=mid-1;
e=e%10000003;
}
else
{
s=mid+1;
s=s%10000003;
}
}
cout<<ans;
}
