#include <bits/stdc++.h>
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int d[1005][5005];
pair <int, int> v[1005];
int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= n; i ++)
        in >> v[i].first >> v[i].second;
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            d[i][j] = (1 << 30);
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(j - v[i].first <= 0)
                d[i][j] = min(d[i - 1][j], v[i].second);
            else
                d[i][j] = min(d[i - 1][j], d[i - 1][j - v[i].first] + v[i].second);
        }
    }
    out << d[n][m];
    return 0;
}