View Code of Problem 4045

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
int dp[10005];
int v[10005];
int w[10005];
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> v[i] >> w[i];
	}
	for (int i = 0; i < m; i++) {
		for (int j = n; j >= v[i]; j--) {
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	cout << dp[n] << endl;

	return 0;
}