题目来源：
http://acm.hdu.edu.cn/showproblem.php?pid=3433
/*
题目描述: N个人,第i个人完成一个A任务需要时间ai,完成一个B任务需要时间bi，
现在又X个任务A和Y个任务B，求完成所有任务所需要的最短时间。
解法：二分时间t，dp[i][j]表示前i个人完成j个A任务所能够完成的B任务的数量
*/
#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){ //判断在时间t内是否可以完成所有的任务
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个人完成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;
}