#include<cstdio>
using namespace std;
int n,k,i,j,min;
int g[1001],p[1001],profit[50000001],s;
int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d%d",&g[i],&p[i]);
        s+=p[i];
    }
    for(i=1;i<=n;i++){
        for(j=s-g[i];j>=1;j--)
            if(profit[j]!=0&&profit[j]+p[i]<profit[j+g[i]])
                profit[j+g[i]]=profit[j]+p[i];
        if(profit[g[i]]>p[i]||profit[g[i]]==0)
            profit[g[i]]=p[i];
    }
    min=0;
    for(i=1;i<=s;i++)
        if(profit[i]>min)
            min=profit[i];
    printf("%d",min);
    return 0;
}