int cal( vector<int>v , long long int x)
{
    int i , c = 0 ;
    long long int cur = 0;
    for( i = 0 ; i < v.size() ; i++ )
    {
        cur += v[i];
       if( cur > x)
       {
           c++;
           cur = v[i];
       }
        
    }
    return (c + 1);
}
int paint(int A, int B, vector<int> &C) 
{
    int i ;
    long long int mi = -1, sum = 0;
    for( i = 0 ; i < C.size() ; i++)
    {
        sum += C[i];
        mi = max( mi ,(long long ) C[i]);
    }
    
    long long int l = mi, h = sum, m , ans = -1, x , lm = -1;
   /*  if( A == C.size())
    {
        ans = mi;
        goto p;
    }*/
    while( l <= h)
    {
        m = (l + h) / 2;
       
        if( m == lm)
            break;
        x = cal( C, m);
        if( x == A)
        {
            ans = m;
            h = m;
        }
        else if( x > A)
        {
            l = m+1;
        }
        else if( x < A)
        {
            ans = m;
            h = m;
        }
        lm = m;
        
    }
   
    p:
    ans %= 10000003;
    ans *= B%10000003;
    ans %= 10000003;
    return (int)ans;
}