#include <bits/stdc++.h>
using namespace std;
int main(){
    int dp[502][1000002], N, L, c[502], l[502];
    cin >> N >> L;
    for(int i=1;i<=N;i++) cin>>c[i]>>l[i];
    for(int i=1;i<=N;i++)for(int j=0;j<L;j++) dp[i][j]=2147483647;
    dp[1][0]=0;
    for(int i=1;i<=N;i++){
        for(int j=0;j<L;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j+c[i]]+l[i]);
        }
    }
    int nmin=2147483647;
    for(int i=0;i<1000000;i++)nmin=min(dp[N][i],nmin);
    printf("%d",nmin);
    return 0;
}