Algorithm/complete-backup/main.cc

#include <cstring>
#include <iostream>
using namespace std;
#define MAXN 10005
#define M 105
int dp[MAXN];
int w[M], state[M];
int x[M];
int main() {
  int n, W;
  cin >> W >> n;
  for (int i = 1; i <= n; i++)
    cin >> w[i] >> state[i];
  for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= W; j++)
      dp[j] = max(dp[j], dp[j - w[i]] + state[i]);
  cout << dp[W] << endl;
  return 0;
}