https://codeforces.com/contest/2035/problem/E
有个显而易见的结论，要获胜必须升级至少一次武器，要升级武器必须尽可能先升级。
于是设如果最终升级了w次武器，可以得出ans的式子，O(1)可以得出答案。
然后就是暴力枚举w找最少的ans。但是w理论范围属于1~Z，Z的量级在1e8，会TLE。
于是观察式子:

ll get_ans(ll w){
    ll p1 = w*x;
    ll p2 = (w/k)*y;
    ll p3 = 2*z - k*(w/k)*(w/k+1);
    if(p3<=0) return p1+p2;
    return p1+p2+(p3+2*w-1)/(2*w) *y;
}

首先p3一定大于等于0。p3小于等于0意味着在升级的过程中，就已经获胜了，后续的升级显然是不必要的，因此p3小于等于0的情况计算一次之后，可以直接结束枚举了。
再看两个除法式子，如果两个除法值相同的话，显然w越小越好。
因此写两个二分，对两个式子求出最大的w使得两个式子与当前式子相同，取二分结果的最小值，然后下一次枚举的结果是最小值+1。
复杂度就是很怪，根据p3大于等于0肯定有w/k小于1e4。根据w/k肯定有需要枚举的数小于z/k。之后就是p3那个除法式子的复杂度不知道怎么算，实测一下1e8量级的数据只需要枚举大概1e4 1e5这样。总之就过了。

#include<bits/stdc++.h>
#define LOCAL//delete when submit!!!!!!
#define MULTI_TEST

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
ll x,y,z,k;
ll get_ans(ll w){
    ll p1 = w*x;
    ll p2 = (w/k)*y;
    ll p3 = 2*z - k*(w/k)*(w/k+1);
    if(p3<=0) return p1+p2;
    return p1+p2+(p3+2*w-1)/(2*w) *y;
}
ll get_nxt(ll x){

    auto f1 = [&](ll w){
        ll p = 2*z - k*(w/k)*(w/k+1);
        return p<=0?0:(p+2*w-1)/(2*w);
    };

    ll l=x,r=z;
    while(l<r){
        ll mid =(l+r+1)/2;
        if(f1(mid)<f1(x)) r=mid-1;
        else l=mid;
    }
    ll l2 = x;r=z;
    while(l2<r){
        ll mid = (l2+r+1)/2;
        if(mid/k > x/k) r=mid-1;
        else l2=mid;
    }   
    cout<<l<<" "<<l2;
    return min(l,l2);
}
void solve(){
    cin>>x>>y>>z>>k;
    ll ans = 1e18;
    ll posx=0;
    for(ll w=1;w<=z;){
        ll p = 2*z - k*(w/k)*(w/k+1);

        ans = min(ans,get_ans(w));
        if(p<=0) break;
        w = get_nxt(w)+1;
        cout<<" "<<w<<endl;
    }
    cout<<ans<<endl;
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}