#include
#include
#include
using namespace std;
bool isPossible(int *arr,int n,int m,int curr_min)
{
int student_used=1;
int pages_reading=0;
for(int i=0;i<n;i++)
{
if(pages_reading+arr[i]>curr_min)
{
student_used++;
pages_reading=arr[i];
if(student_used>m)
return false;
}
else
pages_reading=pages_reading+arr[i];
}
return true;
}
int find_pages(int *arr,int n,int m)
{
int sum=0;
for(int i=0;i<n;i++)
sum=sum+arr[i];
int l=arr[n-1];
int h=sum;
int ans=INT_MAX;
while(l<=h)
{
int mid=(l+h)/2;
if(isPossible(arr,n,m,mid))
{
ans=min(ans,mid);
h=mid-1;
}
else
l=mid+1;
}
return ans;
}
int main()
{
int t,i,j,n,m;
cin>>t;
for(i=0;i<t;i++)
{
cin>>n>>m;
int *arr=new int[n];
for(j=0;j<n;j++)
cin>>arr[j];
cout<<find_pages(arr,n,m);
}
}