#include<bits/stdc++.h>

using namespace std;
#define int long long

const int maxn = 1e5 + 5;
int a[maxn],n,m;

int sqz(int tt,int p)
{
    if(tt % p == 0) {
        return tt / p;
    } else {
        return tt / p + 1;
    }
}

bool ok(int x)
{
    int now = 0,t = 0,num = 0;
    for(int i = 1;i <= n;i++)
    {
        now = t;
        t = 0;
        if(i == n && now >= x){
            continue;
        }
        if(now + a[i] >= x){
            num++;
            if(num > m) {
                return 0;
            }
            continue;
        }

        int cnt = sqz(x - now,a[i]);
        num += (cnt * 2 - 1);
        t = a[i+1] * (cnt - 1);

        if(num > m) {
            return 0;
        }
    }
    return 1;
}

void solve()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
    }

    int res = 0;

    //cout << ok(2) << endl;
    //cout << ok(3) << endl;
    //cout << ok(4) << endl;

    int l = 0,r = 1e18 + 5;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(ok(mid)) {
            //cout << mid << endl;
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t;
    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}