1A-C.cpp

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pii;

template<typename T>
using pq_gt = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using pq_lt = priority_queue<T, vector<T>, less<T>>;

#define se second
#define fi first
#define pb push_back

int W[110];
int H[110];
long double diag[110];
int len[110];

int main() {
    ios::sync_with_stdio(false);
    int t; 
   	cin>>t;
   	for(int tt = 1; tt<=t; tt++) {
   		cout<<"Case #"<<tt<<": ";
   		map<int,long double> dp;
   		long long int temp = 0;
   		int N,P;
   		cin>>N>>P;
   		for(int i = 0; i < N; ++i) {
   			cin>>W[i]>>H[i];
   			temp +=((W[i]+H[i])*2);
   			diag[i] = 2*sqrt((long double)((W[i]*W[i]+H[i]*H[i])));
   			len[i] = min(2*W[i],2*H[i]);
   		}
   		dp[0] = temp;
   		long double maxi = temp;
   		for(int i = 0; i < N; ++i) {
   			vector<int> keys;
   			for(pii p:dp) {
   				keys.pb(p.fi);
   			}
   			for(int j:keys) {
   				if(j+len[i]+temp <= P) {
	   				long double dtemp = dp[j+len[i]];
	   				dp[j+len[i]] = max(dtemp, dp[j] + diag[i]);
	   				maxi = max(maxi, dp[j+len[i]]);
	   			}
   			}
   		}
   		cout<<fixed<<setprecision(10);
   		if(maxi > P) {
   			cout<<P<<endl;
   		} else {
   			cout<<maxi<<endl;
   		}
   	}
}