#include
using namespace std;
bool issafe(int *cumarr,int num,int students,int &maxnum,int lastindex)
{
maxnum=0;
int i=-1,j=0;int flag=1;
while(students>0)
{
if(cumarr[j]-cumarr[i]>=num)
{
if(maxnum<=cumarr[j]-cumarr[i])
{
//cout<<"max value updating for “<<num<<” at "<<cumarr[j]-cumarr[i]<<endl;
maxnum=cumarr[j]-cumarr[i];
}
i=j;
j++;
students–;
}
else
j++;
if(students>0 && j>lastindex)
{
flag=0;
break;
}
}
if(flag)
return true;
else
return false;
}
int bookdistribution(int *cumarr,int lastindex,int students)
{
int low=0;
int high=cumarr[lastindex];int ans=0;
while(high>=low)
{int maxnum=0;
int num=low+(-low+high)/2;
if(issafe(cumarr,num,students,maxnum,lastindex)) //(int *cumarr,int num,students,int &maxnum,int lastindex)
{
low=num+1;
ans=maxnum;
}
else
high=num-1;
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int *arr=new int[n];
arr[-1]=0;
int students;
cin>>students;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
arr[i]=a+arr[i-1];
}
cout<< bookdistribution(arr,n-1,students)<<endl; //(int *cumarr,int lastindex,int students)
}
return 0;
}