The 17th Heilongjiang Provincial Collegiate Programming Contest A(思维 + 二分)

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
	int a, b, n, m, h;
	std::cin >> a >> b >> n >> m >> h;
	
	i64 cnt = i64(n / b) * (h - a);
	if (cnt >= m - 1) {
		std::cout << n + 1 << "\n";
		return ;
	}
	
	if (h == b) {
		std::cout << n + m - cnt << "\n";
		return ;
	}
	
	int lo = 0, hi = m - 1 - cnt;
	auto check = [&](int k) -> bool {
		int A = n % b;
		int B = m - cnt - k;
		if (k < h - b) {
			return true;
		}
		if (k % (h - b) == 0) {
			return A + B >= i64((k + h - b - 1) / (h - b) - 1) * b + 
			(b + 1) / 2;
		} else {
			return A + B >= i64((k + h - b - 1) / (h - b)) * b;
		}
	};
	
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		if (check(mid)) {
			lo = mid;
		} else {
			hi = mid - 1;
		}
	}
	i64 up = (i64((lo + h - b - 1) / (h - b)) + n / b) * b;
	i64 down = n + m - cnt - lo;
	std::cout << std::max(up, down) << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int T;
	std::cin >> T;
	
	while (T--) {
		solve();
	}
	return 0;
}