【題解】ZeroJudge b131: NOIP2006 2.开心的金明

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

int main(){
	int N, m;
	cin >> N >> m;
	int v[m], w[m];
	for (int i=0; i<m; i++){
		cin >> v[i] >> w[i];
	}
	int dp[2][N+1];
	memset(dp, 0, sizeof(dp));
	int idx = 0;
	for (int i=0; i<m; i++){
		for (int j=0; j<=N; j++){
			if (j < v[i]) {
				dp[idx^1][j] = dp[idx][j];
			} else {
				dp[idx^1][j] = max(dp[idx][j], dp[idx][j - v[i]] + v[i] * w[i]);
			}
		}
		idx ^= 1;
	}
	cout << dp[idx][N] << '\n';
	return 0;
}

N, m = map(int, input().split())
v = []
w = []
for _ in range(m):
    V, W = map(int, input().split())
    v.append(V)
    w.append(W)
    
dp = [[0 for j in range(N+1)] for i in range(2)]
idx = 0
for i in range(m):
    for j in range(N+1):
        if j < v[i]:
            dp[idx^1][j] = dp[idx][j]
        else:
            dp[idx^1][j] = max(dp[idx][j], dp[idx][j - v[i]] + v[i] * w[i])
    idx = idx^1
    
print(dp[idx][N])