#include <fstream>

using namespace std;

ifstream cin ("energii.in");
ofstream cout ("energii.out");

const int INF = 1e9;
const int N = 5000;
int dp[N + 1][N + 1];

struct clasa
{
    int e, cost;
} a[N + 1];

int n, energ;

int main()
{
    cin >> n >> energ;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].e >> a[i].cost;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= energ; ++j)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= energ; ++j)
            if (j >= a[i].e && dp[i - 1][j - a[i].e] + a[i].cost < dp[i - 1][j])
                dp[i][j] = dp[i - 1][j - a[i].e] + a[i].cost;
            else
                dp[i][j] = dp[i - 1][j];
    cout << dp[n][energ] << "\n";
    return 0;
}