#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 num = 0;
    int t = 0;
    for(int i = 1;i <= n;i++) {
        if(a[i] + t >= x) {
            if(i == n) {
                break;
            }
            t = 0;
            num++;
        } else {
            num++;
            int sb = sqz(x - a[i] - t,a[i]);
            num += (2 * sb);
            t = a[i + 1] * sb;
        }
        //cout << num << " " << t << endl;
    }
    if(num <= m) {
        return true;
    }
    return false;
}

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

    int res = 0;

    //cout << ok(20) << endl;
    //cout << ok(19) << endl;
    //cout << ok(18) << 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;
}