#include <stdio.h>
int n, m;
int arr[1010];
int dp[1010];
bool check(int x)
{
    int sum = 0;
    for(int i = 1; i <= n; i++)
        dp[i] = m + 1;
    dp[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        sum = 0;
        for(int j = i; j > 0; j--)
        {
            sum += arr[j];
            if(sum <= x && dp[i] > dp[j - 1] + 1)
                dp[i] = dp[j - 1] + 1;
        }
    }
    return dp[n] <= m;
}
int main()
{
    int cs;
    scanf("%d", &cs);
    while(cs--)
    {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        if(n == 1)
        {
            printf("%d\n", arr[1]);
            continue;
        }
        int low = -100000, high = 100000, ans = -1;
        int mark = 1;
        while(low <= high)
        {
            int mid = (low + high) / 2;
            if(check(mid))
            {
                ans = mid;
                high = mid - 1;
            }
            else low = mid + 1;
        }
        printf("%d\n", ans);
    }
}