/* Infoarena energii - knapsack dp
problema clasica: cel mai mare profit cu greutatea sub limita admisa
problema curenta: cel mai mic cost cu energia produsa cel putin egala

### Explanation

This problem differs from the classic knapsack problem in the following ways:

1. **Objective**: In the classic knapsack problem, the objective is to maximize the profit without exceeding the weight limit. In this problem, the objective is to minimize the cost while ensuring that the total energy produced is at least the required amount.

2. **Constraints**: The classic knapsack problem has a weight limit that should not be exceeded. In this problem, there is a minimum energy requirement that must be met or exceeded.

3. **Input and Output**: The input for this problem includes the number of generators, the required energy, and for each generator, the energy it produces and the cost. The output is the minimum cost to produce at least the required energy.

### [energii.cpp](file:///x:/code/cpp/Dynamic%20Programming/Knapsack/knapsack/energii.cpp)

Add the implementation for solving the problem using dynamic programming.

*/

#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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

int main()
{
    int n, W;
    cin >> n >> W;
    vector<int> E(n + 1), C(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> E[i] >> C[i];

    // Initialize dp array with a large value (infinity)
    vector<int> dp(W + 1, INT_MAX);
    dp[0] = 0; // Cost to produce 0 energy is 0

    // Dynamic programming to find the minimum cost
    for (int i = 1; i <= n; ++i)
        for (int j = W; j >= 0; --j)
            if (dp[j] != INT_MAX)
                if (j + E[i] <= W)
                    dp[j + E[i]] = min(dp[j + E[i]], dp[j] + C[i]);
                else
                    dp[W] = min(dp[W], dp[j] + C[i]);

    if (dp[W] == INT_MAX)
        cout << -1;
    else
        cout << dp[W] << endl;

    return 0;
}