View Code of Problem 1058

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

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

bool sol(int x){
    int i,j,k,bound;
    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    for(i = 1;i <= n;i++){
        bound = x/a[i];
        for(j = 0;j <= m;j++){
            for(k = 0;k <= j&&k <= bound;k++){
                if(dp[i-1][j-k]==-1) continue;
                dp[i][j] = max(dp[i][j],dp[i-1][j-k]+(x-k*a[i])/b[i]);
            }
        }
    }
    return dp[n][m]>=m;
}

int main(){
    int i,j,cas;
    scanf("%d",&cas);
    for(int T=1;T<=cas;T++){
        scanf("%d%d",&n,&m);
        for(i = 1;i <= n;i++) scanf("%d%d",&a[i],&b[i]);
        int lb,rb,mid;
        lb = 0,rb = 50001;
        while(rb-lb>1){
            mid = (lb+rb)>>1;
            if(sol(mid)) rb = mid;
            else lb = mid;
        }
        printf("Case %d: %d\n",T,rb);
    }

    return 0;
}