贪心+二分入门题：
#include <iostream>
#include<string.h>
#include<algorithm>
#include<cstdio>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
void in(int &a)
{
char ch;
while((ch=getchar())<'0'||ch>'9');
for( a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';
}
/*int d,x,y;
void extend_gcd(int a,int b,int& d,int& x,int& y)
{
if(b==0)
{
d=a;
x=1;
y=0;
return;
}
extend_gcd(b,a%b,d,x,y);
int t=x-(a/b)*y;
x=y;
y=t;
}
int main()
{
int a,b;
while(cin>>a>>b)
{
extend_gcd(a,b,d,x,y);
while(x<0) x+=b;
cout<<x<<endl;
}
return 0;
}
*/
#define N 10005
int p[N],n,m,maxx,sum;
void input()
{
maxx=-1,sum=0;
for(int i=0;i<n;++i)
{
cin>>p[i];
if(maxx<p[i]) maxx=p[i];
sum+=p[i];
}
}
bool _test(int t)
{
bool flag=true;
int s=0,num=0;
for(int i=0;i<n;++i)
{
if(p[i]>t)
{
flag=false;
break;
}
if(s+p[i]>t)
{
s=p[i];
num++;
if(num>m-1)
{
flag=false;
break;
}
}
else
{
s+=p[i];
}
}
return flag;
}
int bin_search()
{
int l=maxx,r=sum;
while(l<=r)
{
int mid=(l+r)>>1;
if(_test(mid)) r=mid-1;
else l=mid+1;
}
return l;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
input();
cout<<bin_search()<<endl;
}
return 0;
}