Pagini recente » Cod sursa (job #2577145) | Cod sursa (job #2892148) | Cod sursa (job #2542804) | Cod sursa (job #2326851) | Cod sursa (job #21451)
Cod sursa(job #21451)
#include<stdio.h>
#include<string.h>
#define maxl 200
long L,n;
long sal[maxl+1][maxl+1];
long v[101][2];
long sol(long a)
{
long i,k,j,l;
memset(sal,0,sizeof(sal));
sal[0][0]=1;
for(k=1;k<=n;k++)
{
for(i=L;i>=0;i--)
{
for(j=L;j>=0;j--)
{
if(sal[i][j])
for(l=0;l*v[k][0]<=a;l++)
{
sal[i+l][j+(a-l*v[k][0])/v[k][1]]=1;
if(i+l>=L && j+(a-l*v[k][0])/v[k][1]>=L)
return 1;
}
}
}
}
return 0;
}
long cauta(long a,long b)
{
if(a==b) return a;
long mij=(a+b)/2;
if(sol(mij)) return cauta(a,mij);
else return cauta(mij+1,b);
}
int main()
{
long x,i;
freopen("lapte.in","rt",stdin);
//freopen("lapte.out","wt",stdout);
scanf("%ld%ld",&n,&L);
for(i=1;i<=n;i++)
scanf("%ld%ld",&v[i][0],&v[i][1]);
x=cauta(1,L);
printf("%ld\n",x);
return 0;
}