題目來(lái)源：
http://acm.hdu.edu.cn/showproblem.php?pid=3433
/*
題目描述: N個(gè)人,第i個(gè)人完成一個(gè)A任務(wù)需要時(shí)間ai,完成一個(gè)B任務(wù)需要時(shí)間bi，
現(xiàn)在又X個(gè)任務(wù)A和Y個(gè)任務(wù)B，求完成所有任務(wù)所需要的最短時(shí)間。
解法：二分時(shí)間t，dp[i][j]表示前i個(gè)人完成j個(gè)A任務(wù)所能夠完成的B任務(wù)的數(shù)量
*/
#include <stdio.h>
#include <memory>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <time.h>
#include <limits>
using namespace std;
#define XY 205
#define N 55
#define inf 0x7fffffff
int a[N], b[N], dp[XY], n, X, Y;
bool check(int t){ //判斷在時(shí)間t內(nèi)是否可以完成所有的任務(wù)
int i, j, k, kMax;
for(i = 1; i <= X; i++) dp[i] = -1;
dp[0] = 0;
for(i = 0; i < n; i++){
kMax = min(X, t / a[i]);
if(dp[X] >= Y) return true;
for(j = X; j >= 0; j--){
for(k = 0; k <= kMax && j - k>= 0; k++){ //第i個(gè)人完成k件
if(dp[j-k] < 0) continue;
dp[j] = max(dp[j], dp[j - k] + (t - k * a[i]) / b[i]);
}
}
}
return dp[X] >= Y;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int t, i,ca, low, high, mid;
scanf("%d", &t);
for(ca = 1; ca <= t; ca++){
scanf("%d%d%d", &n, &X, &Y);
low = 0;
high = inf;
for(i = 0; i < n; i++){
scanf("%d%d", a+i, b+i);
high = min(high, a[i] * X + b[i] * Y);
}
while(low <= high){
mid = (low + high) >> 1;
if(check(mid)) high = mid - 1;
else low = mid + 1;
}
printf("Case %d: %d\n", ca, high + 1);
}
return 0;
}