/* Algoritm problema "Transporturi" :

   DACA VREI SA INVETI CEVA NOU POTI SA TE UITI PESTE ACEST PROGRAM DEOARECE ESTE FOARTE BINE EXPLICAT

   DACA VREI DOAR O SURSA DE 100 PUNCTEO POTI LUA FARA SA INVETI NIMIC NOU

   E ALEGEREA TA!

   Tinem un AIB cu volumele saltelelor pentru a calcula eficient sumele partiale

   Cautam pe intervalul nmax -> suma volumelor un numar minim care sa ne dea un raspuns bun

   Complexitate :

   pentru adaugarea in AIB : O ( n * log n )
   pentru cautarea binara pe interval + cautarea de suma partiala : O ( log totalsum * log mid )

   Pertotal undeva la O ( n * log totalsum )
   Multumim Doamne !
*/
#include <stdio.h> /// pentru fread() + fprintf()
#include <ctype.h> /// pentru isdigit()
#include <limits.h> /// pentru INT_MAX
#include <math.h> /// pentru log2()
#define  Nadejde  16384 /// dimensiunea AIB-ului
#define  Dragoste 4096 /// marimea bufferului

char buff[ Dragoste ] ; /// bufferul oferit de sistem
char c ; /// un caracter
short pos = Dragoste ; /// pozitia in buff[]
int   i ; /// un index
int   lg ; /// logaritm din 2
int   lo ; /// folosit la cautarea binara
int   hi ; /// folosit la cautarea binara
int   mid ; /// folosit la cautarea binara
int   poz ; /// pozitia in AIB
int   num ; /// citim stiva
int   LOG ; /// folosit la Add()
int   nmax ; /// salteaua maxima
int   trans ; /// cate transporturi facem maxim cu camionul
int   gasit ; /// raspunsul e bun?
int   found ; /// aici memoram raspunsul dorit
int   answer ; /// raspunsul
int   result ; ///rezultatul la solutiacu "mid"
int   mattress ; /// numarul de saltele
int   Fenwick[ Nadejde + 1 ] ; /// AIB -ul nostru
long long int Sum ; /// suma partiala in AIB
long long int BigSum ; /// folosit la Solve()
long long int totalsum ; /// suma totala

/// Citire parsata
char getChar( FILE *fin )
{
     if( pos == Dragoste )
       {
         /// citim fisierul
         fread( buff , 1 , Dragoste , fin ) ;
         pos = 0 ;
       }
     /// returnam urmatorul caracter
     return buff[ pos ++ ] ;
}
/// FILE + Laser :)
inline void fLaser( FILE *fin , int *result )
{
       *result = 0 ;
       /// cat timp nu e cifra
       do{
          c = getChar( fin ) ;
       }while( !isdigit( c ) ) ;
       /// construim numarul cand "c" e cifra
       do{
          *result = ( *result << 3 ) + ( *result << 1 ) + c - '0' ;
          c = getChar( fin ) ;
       }while( isdigit( c ) ) ;
}
/// adugarea in AIB
void Add( int val , int x )
{
     do{
        Fenwick[ x ] += val ;
        x += x & -x ;
     }while( x <= LOG ) ; /// pana nu am iesit din AIB
}
/// cautarea binara a sumei partiale
int BinarySearch( long long int val )
{
    int x = 0 ;
    int interval = LOG ;
    /// cat timp mai avem un interval
    while( interval )
         {
           /// daca am gasit ceva bun
           if( Fenwick[ x + interval ] <= val )
             {
               val -= Fenwick[ x + interval ] ;
               x += interval ;
             }
           /// injumatatim mereu intervalul
           interval >>= 1 ;
         }

    return x ;
}
/// luam suma partiala din AIB la o anumita pozitie
int getSum( int x )
{
    int sum = 0 ;

    while( x )
         {
           sum += Fenwick[ x ] ;
           x &= ( x - 1 ) ;
         }
    return sum ;
}
/// Functia de rezolvare o problemei
int Solve( int vol )
{
     gasit = 0 ; /// daca incap la inceput in camion
     answer = 0 ; /// cate transporturi facem
     BigSum = vol ;
     /// cat timp mai avem saltele
     while ( BigSum < totalsum && !gasit )
           {
             /// cautam binar suma partiala pana la salteaua BigSum
             poz = BinarySearch ( BigSum ) ;

             if( poz )
               {
                 /// vedem cate transporturi facem
                 Sum = getSum( poz ) ;
                 answer ++ ;

                 BigSum = Sum + vol ;
                 if( BigSum >= totalsum )
                   {
                     answer ++ ;
                     gasit = 1 ;
                   }
               }
             else
               {
                 gasit = 1 ;
               }
           }
     /// returnam transporturile
     return answer ;
}
/// int main()
int main( )
{
    /// variabila in care memoram raspunsul
    found = INT_MAX ;
    /// Deschidere fisiere *C*
    FILE *fin = fopen( "transport.in" , "r" ) ;
    FILE *fout = fopen( "transport.out" , "w" ) ;
    /// Citim datele de intrare parsat
    fLaser( fin , &mattress ) ;
    fLaser( fin , &trans ) ;
    /// calculam logaritmii
    lg = log2( mattress );
    LOG = ( 1 << ( lg + 1 ) ) ;
    /// Bagam in AIB saltelele
    for( i = 1 ; i <= mattress ; i ++ )
       {
         fLaser( fin , &num ) ;
         totalsum += num ;

         if( num > nmax )
             nmax = num ;

         Add( num , i ) ;
       }
    /// Facem cautarea binara pe intervalul nmax -> suma saltelelor
    lo = nmax ;
    hi = totalsum ;

    while ( lo <= hi )
          {
            /// calculam mijlocul
            mid = lo + ( ( hi - lo ) >> 1 ) ;
            /// memoram cate transporturi facem cu mid
            result = Solve( mid ) ;
            /// daca nu e zero si e mai mic decat ar trebui ne mutam la dreapta la numere mai mari
            if( result && result <= trans )
              {
                hi = mid - 1 ;
                /// luam mereu cel mai mic numar de transporturi
                if( mid < found )
                    found = mid ;
              }
            /// daca nu e bun coboram la numere mai mici
            else
              {
                lo = mid + 1 ;
              }
          }
    /// Afisam rezultatul dorit + mereu linie noua
    fprintf( fout , "%d\n" , found ) ;
    /// Multumim Doamne!
    /// fprintf( fout , "Gresit-am Doamne inaintea Ta si nu sunt vrednic sa ma numesc Fiul Tau . Fa-ma ca pe unul din argatii Tai" ) ;
    /// Inchidem fisierele
    fclose( fin ) ;
    fclose( fout ) ;
    /// dai return 0
    return 0 ;
}