#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

void solve(){
    ll n, k;
    cin >> n >> k;
    vector<ll> v(n);
    for(auto &x : v) cin >> x;

    if(k == 1){
        ll ans = v.front();
        for(int i = 0;i + 1 < n;i += 1){
            ans = max(ans, v[i] + v[i + 1]);
        }
        cout << ans;
        return;
    }

    // tot % k = 0;
    // v[i] pairs with v[i - 1] or v[i + 1] but not both
    // in a row

    auto check = [&](ll col){

        // col - number of people in a row
        ll prev = 0,done = 0;

        for(int i = 0;i < n;i += 1){
            if(prev >= col){
                done += prev/col;
            }
            ll left = prev % col;
            if(left + v[i] < col){
                // think
                // nothing can be done if this path is choosen
                if(done >= k){
                    return true;
                }
                prev = 0,done = 0; // take other options
            }
            else{
                prev = left + v[i] - col;
                ++done;
            }
            // cerr << done << ' ' << prev << " NEXT\n";
        }
        done += prev/col;
        // cerr << done <<  ' ';

        return (done >= k);
    };

    ll l = 1,r = 1e12;
    ll ans = 0;
    while(l <= r){
        ll mid = (l + r)/2ll;

        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }

    // cerr << check(28);
    // cerr << '\n';
    // for(ll nk = 21;nk <= 28;nk += 1){
    //     cout << check(nk) << ' ';
    // }

    cout << (ans * 1ll * k);


}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while(t--){
        solve();
        cout << '\n';
    }
}