Good Key, Bad Key

#include <bits/stdc++.h>
using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ll  long long

void solve();

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

    ll t;
    t=1;
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

ll getAns(ll i, vector<ll> vec, ll &k, ll &n, ll bad, vector<vector<ll>> &dp){
    if(i>=n){
        return 0;
    }

    if(dp[i][bad]!=-1){
        return dp[i][bad];
    }

    ll t = vec[i];
    for(ll a=0; a<bad; ++a){
        t/=2;
    }

    ll choice1 = getAns(i+1, vec, k, n, bad, dp) + t - k;


    ll choice2 = getAns(i+1, vec, k, n, bad+1, dp) + t/2;

    return dp[i][bad] = max(choice2, choice1);
}

void solve(){
    ll n, k; cin>>n>>k;
    vector<ll> vec(n);
    vector<vector<ll>> dp(n, vector<ll> (n, -1));

    for(ll i=0; i<n; ++i){
        cin>>vec[i];
    }

    ll ans = getAns(0, vec, k, n, 0, dp);
    cout<<ans<<endl;
}