#include <bits/stdc++.h>
#define Nmax 5005
using namespace std;

int n, w, v[Nmax], DP[5005], x, y;

int main()
{
    ios::sync_with_stdio(false);
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);

    cin >> n >> w;
    memset(DP,0x3f,sizeof(DP));
    DP[0] = 0;
    for (int i=1;i<=n;i++){
        cin >> x >> y;
        for (int j=w;j>=x;j--)
            DP[j] = min(DP[j], DP[j-x] + y);
    }
    cout << DP[w] << '\n';

    return 0;
}