#include <numeric>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

int MinCostRucsac(int W, vector<int> &energie, vector<int> &cost, int g);

int main()
{
    int g, w;
    vector<int> energie;
    vector<int> cost;// second = costul producerii de energie

    fin >> g >> w;
    energie.reserve(g + 1);
    cost.reserve(g + 1);
    for (int i = 0; i < g; ++i)
        fin >> energie[i] >> cost[i];
        
    fout << MinCostRucsac(w, energie, cost, g);

    return 0;
}


int MinCostRucsac(int W, vector<int> &energie, vector<int> &cost, int g)
{
    int max_energie = 0;
    for (int i = 0; i < g; ++i)
        max_energie += energie[i];
    int dp_size = max(W, max_energie);
    const long long INF = 10001;
    vector<long long> dp(dp_size, INF); // dp[i] = costul minim pt. a obtine grutatea i
    dp[0] = 0;

    for(int i = 0; i < g; ++i)
        for(int e = dp_size - 1; e >= energie[i]; --e)
            if(dp[e - energie[i]] + (long long)cost[i] < dp[e])
                dp[e] = dp[e - energie[i]] + (long long)cost[i];

    long long min_cost = INF;
    for(int e = W; e < dp_size; ++e)
        if(dp[e] < min_cost)
            min_cost = dp[e];

    cout <<"max_energie: " << max_energie << '\n';
    cout << "min cost: " << min_cost << '\n';
    for(auto e : dp)
        cout << e << ' '; 


    if(min_cost == INF)
        return -1; // Indicates no possible subset meets the requirement

    return min_cost;

}