#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000000 + 10;
int a[N];
int n,m;
bool check(int x)
{
    vector<int>d(n+10,0);
    int res=0,last=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>=x)continue;
        if(d[i]<x&&d[i+1]<x&&i<n)
        {
            int op1=ceil((double)(x-d[i])/(double(a[i])));
            res+=(op1-1)*2+(i-last);
            if(op1==1)
            {
                last=i;
                d[i]=x;
                if(res>m)return 0;
                continue;
            }
            last=i;
            if(res>m)return 0;
            d[i]=x;
            d[i+1]=(op1-1)*a[i+1];
            continue;
        }
        if(d[i]<x)
        {
            int op1=ceil((double)(x-d[i])/(double(a[i])));
            res+=(op1-1)*2+(i-last);
            if(op1==1)
            {
                last=i;
                d[i]=x;
                if(res>m)return 0;
                continue;
            }
            last=i;
            if(res>m)return 0;
            d[i]=x;
        }
    }
    return 1;
}
void se()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    //check(4);
    int l=0,r=1e15;
    while (l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        se();
    }
    return 0;
}