#include <bits/stdc++.h>
#define INF 23000
using namespace std;

int max1(int a, int b) { return (a > b) ? a : b; }
int n, W, val[1002], wt[1002], a[1001][5002];

int knapSack(int W, int wt[], int val[], int n)
{


    if (n == 0 || W == 0)
        return -1;


    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);


    else
        return max1(val[n - 1] + knapSack(W - wt[n - 1],wt, val, n - 1),knapSack(W, wt, val, n - 1));
}


int main()
{

    freopen("energii.in", "r", stdin);
    freopen("energii.out", "w", stdout);
    int s;
    scanf("%d %d",&n,&W);
    for(int i = 1; i <= n; i++) {
        scanf("%d %d",&wt[i],&val[i]);
    }
    for(int i = 1; i <= n;i++) {
        for(int j = 1; j <= W;j++) {
                 s = INF;
            for(int k = 1; k <= n ;k++) {
                if(wt[k] <= j) {

                    if(s > val[k] + a[i-1][j - wt[k]])
                        s = val[k] + a[i-1][j - wt[k]];

                }

            }
            a[i][j] = s;
        }
    }
    printf("%d",a[n][W]);
    return 0;
}