View Code of Problem 1058

/*
参考链接  ： http://www.cnblogs.com/jianglangcaijin/archive/2012/10/22/2734212.html
*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define bug printf("hihi\n")

#define eps 1e-12

typedef __int64 ll;

using namespace std;
#define N 105

int n,m;
int a[N],b[N];
int dp[N];

int judge(int mid)
{
    int i,j;
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        int t=mid/a[i];   //对于第i个人，可以做t个a[i],拿出s个来做b[i]
        for(int v=m;v>=0;v--)
           for(int s=0;s<=t&&s<=v;s++)
               if(dp[v-s]!=-1)
                  dp[v]=max(dp[v],dp[v-s]+(mid-s*a[i])/b[i]);
    }
    return dp[m]>=m;
}

int main()
{
    int i,j,t,ca=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            scanf("%d%d",&a[i],&b[i]);
        int le,ri,ans;
        le=0;
        ri=a[1]*m+b[1]*m;
        while(le<=ri)
        {
            int mid=(le+ri)>>1;
            if(judge(mid))
            {
                ans=mid;
                ri=mid-1;
            }
            else
            {
                le=mid+1;
            }
        }
        printf("Case %d: %d\n",++ca,ans);
    }
   return 0;
}