fhc2016r1_b.cpp

#include <queue>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <iterator>
#include <cmath>
#include <tuple>
#include <stack>
#include <iomanip>
#include <string>
#include <vector>
#include <limits>
using namespace std;

template<class T = int,T divided_by = 10>
constexpr T PINF(){ return std::numeric_limits<T>::max()/divided_by; }
template<class T = int,T divided_by = 10>
constexpr T MINF(){ return std::numeric_limits<T>::lowest()/divided_by; }

long long solve(){
	long long l,n,m,d;
	cin >> l >> n >> m >> d;
	vector<long long> w(n);
	for(long long i = 0; i < n; ++i){
		cin >> w[i];
	}
	//にぶたんすにぺっと
	long long invalid_X,valid_X,middle_X;
	
	//↓書き換える
	invalid_X = 0;     //にぶたん開始点1 : invalidなX
	valid_X	 = PINF<long long>();  //にぶたん開始点2 : validなX
	bool check_invalid_flag = true;	//invalid_Xがvalidかつそれが答えになる可能性
	auto is_valid = [&](long long times){	//validのときtrueを返す関数
		long long washed = 0;
		for(long long i = 0; i < n; ++i){
			washed += times/w[i];
		}
		if(l<=washed) return true;
		return false;
	};
	//↑終わり
	
	if(check_invalid_flag&&is_valid(invalid_X)){
		valid_X=invalid_X;
	}else{
		while(1<abs(valid_X-invalid_X)){
			middle_X = (valid_X+invalid_X)/2;
			if(is_valid(middle_X)){
				valid_X=middle_X;
			}else{
				invalid_X=middle_X;
			}
		}
	}
	//にぶたんすにぺっとおわり

	long long wash_t = valid_X;
	multiset<long long> launds_t;
	for(long long i = 0; i < n; ++i){
		long long loop = wash_t/w[i];
		for(long long j = 0; j < loop; ++j){
			launds_t.insert(w[i]*(j+1));
		}
	}

	priority_queue<long long,vector<long long>,greater<long long>> pq;
	long long done = 0,last = 0;
	for(auto t : launds_t){
		if(pq.size()<m){
			last = t+d;
			pq.push(last);
		}else{
			long long p = pq.top(); pq.pop();
			if(p<t){
				last = t+d;
			}else{
				last = p+d;
			}
			pq.push(last);
		}
		done++;
		if(done==l) break;
	}

	return last;
}

int main() {
	cin.tie(nullptr); ios::sync_with_stdio(false);
	//cout << fixed << setprecision(10);

	int t;
	cin >> t;
	for(int i = 0; i < t; ++i){
		cout << "Case #" << i+1 << ": " << solve() << endl;
	}
  return 0;
}