/* Rezolvarea e dinamica. S(i,j)=volumul minim pt transportul primelor i
saltele in cel mult j zile. Se observa ca pt j=1, volumul este suma primelor
i volume. In rest, salteaua i o putem transporta:
-la un loc cu volumu maxim din i-1, in cel mult j-1 zile.
-impreuna cu celelalte saltele, care nu fac parte din transportul maxim.
-separat=un nou transport, doar pt salteaua asta.
Am redus memoria, obervand ca am nevoie doar de 2 linii.
*/

#include<stdio.h>
FILE*f=fopen("transport.in","r");
FILE*g=fopen("transport.out","w");
int a[16002],n,k,v[16002],old[16002],news[16002];
int max(int a, int b)
   {
   if(a>b) return a;
   else return b;
   }
int min(int a, int b, int c)
   {
   if(a<=b && a<=c) return a;
   else if(b<=a && b<=c) return b;
   else return c;
   }
void read()
   {
   int i,j;
   fscanf(f,"%d %d",&n,&k);

   for(i=1;i<=n;++i) fscanf(f,"%d",&v[i]),a[i]=a[i-1]+v[i];
   }
void dinamic()
   {
   int i,j;
   for(i=1;i<=k;++i) old[i]=v[1];
   for(i=2;i<=n;++i)
     {
     news[1]=a[i];
     for(j=2;j<=k;++j)
        news[j]=min(max(v[i],old[j-1]),v[i]+old[j],max(a[i-1]-old[j]+v[i],old[j]));
     for(j=1;j<=k;++j) old[j]=news[j];
     }
   fprintf(g,"%d\n",news[k]);
   }
int main()
   {
   read();
   dinamic();
   return 0;
   }