We need to determine the minimum cost to obtain at least (H) pounds of hay given (n) suppliers. Each supplier offers a bundle weighing (p_i) pounds at cost (c_i), and bundles can be purchased unlimitedly.

Approach 1: State Transition with Conditional Bounds

Standard knapsack formulations maximize value under a weight limit. Here we minimize cost while requiring the total weight to reach or exceed (H). Let (dp[j]) represent the minimum cost to achieve at least (j) pounds. For each supplier (i), when the target (j) exceeds (p_i), we can combine a previous state:

[ dp[j] = \min(dp[j],\ dp[j - p_i] + c_i) ]

When (j \le p_i), a single purchase of bundle (i) satisfies the requirement:

[ dp[j] = \min(dp[j],\ c_i) ]

The (dp) array is initialized to a large value. Complexity is (O(nH)).

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

const int MAXN = 105;
const int MAXW = 50010;
int n, target;
int weight[MAXN], cost[MAXN], dp[MAXW];

int main() {
    scanf("%d%d", &n, &target);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &weight[i], &cost[i]);

    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; ++i) {
        for (int w = 1; w <= weight[i]; ++w)
            dp[w] = min(dp[w], cost[i]);
        for (int w = weight[i] + 1; w <= target; ++w)
            dp[w] = min(dp[w], dp[w - weight[i]] + cost[i]);
    }

    printf("%d", dp[target]);
    return 0;
}

Approach 2: Forward Propagation up to a Threshodl

Instead of pulling from a smaller weight, we can push the effect of a state forward. For each achievable weight (j), purchasing another unit of bundle (i) yields weight (j + p_i). We cap the weight at (H) because exceeding it does not further differentiate the "at least" requirement.

Let (dp[0] = 0). Transition rules:

• If (j + p_i \le H): [ dp[j + p_i] = \min(dp[j + p_i],\ dp[j] + c_i) ]
• If (j + p_i > H): [ dp[H] = \min(dp[H],\ dp[j] + c_i) ]

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

const int MAXN = 105;
const int MAXW = 50010;
int n, required;
int w[MAXN], price[MAXN], best[MAXW];

int main() {
    scanf("%d%d", &n, &required);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &w[i], &price[i]);

    memset(best, 0x3f, sizeof(best));
    best[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int cur = 0; cur <= required; ++cur) {
            int next = min(cur + w[i], required);
            best[next] = min(best[next], best[cur] + price[i]);
        }
    }

    printf("%d", best[required]);
    return 0;
}

Approach 3: Enlarged Capacity with Standard Unbounded Knapsack

We can treat the problem as a classical unbounded knapsack that minimizes cost, but we extend the capacity to accommodate overfill. Because any bundle’s cost is positive, the optimal solution will never exceed (H + \max(c_i)). The excess beyond (H) cannot exceed the weight of one extra bundle in an optimal plan. Thus we set (M = 55010) as a safe upper bound.

After fillling the (dp) array, we scan (dp[i]) for (i) from (H) to (H + C) (where (C = 5000)) and take the minimum.

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

const int MAXN = 105;
const int OFFSET = 5000;
const int MAXM = 55010;
int n, H;
int pkgWeight[MAXN], pkgCost[MAXN], f[MAXM];

int main() {
    scanf("%d%d", &n, &H);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &pkgWeight[i], &pkgCost[i]);

    memset(f, 0x3f, sizeof(f));
    f[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int cap = pkgWeight[i]; cap <= H + OFFSET; ++cap) {
            f[cap] = min(f[cap], f[cap - pkgWeight[i]] + pkgCost[i]);
        }
    }

    int answer = INT_MAX;
    for (int cap = H; cap <= H + OFFSET; ++cap)
        answer = min(answer, f[cap]);

    printf("%d", answer);
    return 0;
}