#include using namespace std; long long solve(vector> AB,long long T){ sort(AB.begin(),AB.end()); long long ret = 1e18; do{ long long t1 = 0,t2 = 0; for(auto [a,b] : AB){ if(t1) t1 += T,t2 += T; t1 += a,t2 = max(t2,t1)+b; } ret = min(ret,t2); }while(next_permutation(AB.begin(),AB.end())); return ret; } random_device rnd; mt19937 mt(rnd()); int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); bool submit = true; while(true){ long long N = mt()%3+3,T = mt()%10+1; if(submit) cin >> N >> T; vector R(N,1); vector> big,small; if(submit) for(auto &r : R) cin >> r; for(int i=0; i> a >> b; if(a <= b) big.push_back({a,b,R.at(i)}); else small.push_back({b,a,R.at(i)}); } sort(big.begin(),big.end()); sort(small.rbegin(),small.rend()); for(auto &[b,a,r] : small) swap(a,b); long long t1 = 0,t2 = 0; for(auto [a,b,r] : big){ if(t1) t1 += T; if(t2) t2 += T; t2 = max(t2,t1+a)+b*r,t1 += a*r; t2 = max(t2,t1+b); } for(auto [a,b,r] : small){ if(t1) t1 += T; if(t2) t2 += T; t2 = max(t2,t1+a)+b*r,t1 += a*r; t2 = max(t2,t1+b); } long long answer = t2; if(submit == false){ vector> AB; for(auto [a,b,r] : big) while(r--) AB.push_back({a,b}); for(auto [a,b,r] : small) while(r--) AB.push_back({a,b}); sort(AB.begin(),AB.end()); long long jury = solve(AB,T); if(answer != jury){ cout << "Wrong" << endl; cout << N << " " << T << endl; for(auto [a,b,r] : big) cout << r << " "; for(auto [a,b,r] : small) cout << r << " "; cout << endl; for(auto [a,b,r] : big) cout << a << " " << b << endl; for(auto [a,b,r] : small) cout << a << " " << b << endl; cout << answer << " " << jury << endl; return 0; } } cout << answer/(24*60) << " " << answer%(24*60)/60 << " " << answer%60 << endl; if(submit) break; } }