Overview

This problem asks us to find the minimum cost to cover at least \(D\) days, given the condition that “any number of food packs can be purchased from each store.”
It can be solved with dynamic programming where \(dp[d] =\) “the minimum cost to cover exactly \(d\) days (where \(d=D\) means \(D\) or more days).”

Analysis

First, since any number of food packs can be purchased from each store, this is a problem closely related to the unbounded knapsack problem.

Key Insight

What we want is not “how much money was spent,” but “how many days’ worth of food can be secured.”
Therefore, it is natural to think in terms of:

• Using the number of days secured as the state
• Adding one food pack at a time to that state

Specifically, we define:

• \(dp[d]\): the minimum cost to cover a total of \(d\) days’ worth of food

However, since the problem only requires “\(D\) days or more,” if \(d + F_i\) exceeds \(D\), it is sufficient to cap it at \(D\).

That is, the transition destination is:

\[ nd = \min(D, d + F_i) \]

---

Why Naive Approaches Are Difficult

1. It is impossible to try all combinations

Since any number of packs can be bought from each store, the number of purchasing patterns is infinite.
Naturally, exhaustive search is not feasible.

2. Greedily choosing the store with the cheapest “price per day” doesn’t work

For example, it might seem like always choosing the store with the smallest \(C_i / F_i\) would work, but
in practice, due to “remainders” and the condition that “exceeding is allowed,” this may not yield the optimal solution.

For example:

• Pack A: 3 days for 4 yen
• Pack B: 5 days for 7 yen
• \(D=6\)

In this case, a simple ratio comparison alone cannot determine the answer.
Since local optimality doesn’t guarantee the global optimal solution in such problems, DP is effective.

---

How to Solve It

Since \(D \le 3000\), a DP with the number of days as the state is fast enough.

From each state \(d\), considering buying one pack from each store, we get the transition:

\[ dp[\min(D, d+F_i)] = \min(dp[\min(D, d+F_i)],\ dp[d] + C_i) \]

By performing this for \(d=0,1,2,\dots,D-1\) in order,
the final \(dp[D]\) gives the answer.

---

Why This Correctly Represents “Unlimited Purchases”

At first glance, it might seem like “each store is only considered once,” but that is not the case.

From state \(d\), you can buy one pack from a store to advance to \(d+F_i\),
and then from that state, buy another pack from the same store again.

In other words, since the “add one pack” operation can be repeated any number of times, the condition of unlimited purchases is naturally represented.

Algorithm

1. Prepare a \(dp\) array of length \(D+1\).
   • \(dp[d]\): the minimum cost to cover exactly \(d\) days
   • However, \(dp[D]\) represents “the minimum cost to cover \(D\) or more days”
2. Initial values:
   • \(dp[0] = 0\)
   • All others are set to a sufficiently large value (\(\infty\))
3. Iterate \(d\) from \(0\) to \(D-1\):
   • If \(dp[d]\) is unreached, skip
   • For each store \((C_i, F_i)\):
     • \(nd = \min(D, d + F_i)\)
     • \(dp[nd] = \min(dp[nd], dp[d] + C_i)\)
4. Output \(dp[D]\)

---

Concrete Example

For example, suppose \(D=7\) and there are 2 stores:

• \((C,F)=(3,2)\)

• \((5,4)\)

• \(dp[0]=0\)

• From 0 days:

  • 2 days for 3 yen
  • 4 days for 5 yen

• From 2 days:

  • 4 days for 6 yen
  • 6 days for 8 yen

• From 4 days:

  • 6 days for 8 yen
  • 7 or more days for 10 yen

Updates proceed in this manner, and ultimately \(dp[7]\) gives the minimum cost.

Complexity

• Time complexity: \(O(ND)\)
• Space complexity: \(O(D)\)

Since \(N,D \le 3000\), \(O(ND) = 9 \times 10^6\), which is sufficiently fast.

Implementation Notes

• To handle “\(D\) days or more,” the transition destination must always be $\( \min(D, d+F_i) \)\( so that any excess beyond \)D$ is consolidated.

• A sufficiently large value of 10**18 is used for initialization.

• By not transitioning when dp[d] is unreached (INF), unnecessary computations are avoided.

• In this implementation, the outer loop iterates over days d and the inner loop over stores,
  naturally expressing unlimited purchases through the form of “adding one pack from the current state.”

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]  # (C, F)

    INF = 10**18
    dp = [INF] * (D + 1)
    dp[0] = 0

    for d in range(D):
        if dp[d] == INF:
            continue
        cur = dp[d]
        for c, f in items:
            nd = D if d + f >= D else d + f
            if dp[nd] > cur + c:
                dp[nd] = cur + c

    print(dp[D])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.