\(\mathrm{dp} _ i[j]\coloneqq i\) 番目までの店で売られている食料パックを使ってちょうど \(j\) 日分の食事を賄うことができる食料を買うために必要な金額の最小値（買うことができなければ \(\infty\)）\(\ (0\le i\le N,0\le j)\) のようにすると、次のような漸化式を得ることができます。

• \(\mathrm{dp} _ 0[0]=0,\mathrm{dp} _ 0[n]=\infty\ (n\gt0)\)
• \(\mathrm{dp} _ {i+1}[j+F _ i]=\min\lbrace\mathrm{dp} _ i[j+F _ i],\mathrm{dp} _ i[j]+C _ i\rbrace\ (0\le i\le N)\)

このとき、求めるものは \(\min\lbrace\mathrm{dp} _ N[D],\mathrm{dp} _ N[D+1],\ldots\rbrace\) です。

ここで、\(j\ge D\) であるような部分をまとめて管理することを考えます。 漸化式を少し変更することで、このような処理を実現できます。

時間計算量は \(O(ND)\) 、空間計算量は DP テーブルを in-place に更新すると \(O(D)\) となります。

実装例は以下のようになります。

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

int main() {
    int N, D;
    cin >> N >> D;

    // dp[i] := i 日分の食料を買うために必要な金額の最小値
    // ただし、dp[D] は D 日分 **以上** の食料を買うために必要な金額の最小値
    // はじめはすべて ∞（答えは 3 × 10^9 より大きくならないので、3 × 10^9 でよい）にしておく
    vector dp(D + 1, 3000000000);
    dp[0] = 0; // 0 日分は 0 円で買える

    for (int n = 0; n < N; ++n) {
        int C, F;
        cin >> C >> F;
        
        // DP テーブルを更新する
        for (int i = 0; i <= D; ++i) {
            dp[min(i + F, D)] = min(dp[min(i + F, D)], dp[i] + C);
        }
    }
    
    // D 日分以上を買うために必要な金額の最小値を出力
    cout << dp[D] << endl;
    return 0;
}

N, D = map(int, input().split())

# dp[i] := i 日分の食料を買うために必要な金額の最小値
 # ただし、dp[D] は D 日分 **以上** の食料を買うために必要な金額の最小値
 # はじめはすべて ∞（答えは 3 × 10^9 より大きくならないので、3 × 10^9 でよい）にしておく
dp = [3000000000 for _ in range(D + 1)]
dp[0] = 0

for _ in range(N):
    C, F = map(int, input().split())
    
    # DP テーブルを更新する
    for i in range(D + 1):
        dp[min(i + F, D)] = min(dp[min(i + F, D)], dp[i] + C)

# D 日分以上を買うために必要な金額の最小値を出力
print(dp[D])