USACO-T041: Score Inflation

/*
ID: mickyta1
TASK: inflate
LANG: C++
*/

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

const int N = 1e4 + 5;

int score[N], tme[N], dp[2][N];

int main(){
    freopen("inflate.in", "r", stdin);
    freopen("inflate.out", "w", stdout);

    int limTime, n;
    scanf("%d%d", &limTime, &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &score[i], &tme[i]);
    }
    for(int i = n; i >= 1; --i){
        int cur = i % 2;
        int nxt = cur ^ 1;
        for(int t = 1; t <= limTime; ++t){
            int mx = dp[nxt][t];
            if(t >= tme[i]){
                mx = max(mx, score[i] + dp[cur][t - tme[i]]);
            }
            dp[cur][t] = mx;
        }
    }
    cout << dp[1][limTime] << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}