01背包问题-简单1

// 0·1背包问题---采药.cpp---洛谷1048

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int N = 1e3 + 10;
int Time[1001];
int mount[101];
int dp[N][N];
int main()
{
	int total_t, num;
	cin >> total_t >> num;
	for (int i = 1; i <= num; i++) {
		cin >> Time[i] >> mount[i];
	}
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= total_t; j++) {
			if (Time[i] <= j) {
				dp[i][j] = max(dp[i - 1][j - Time[i]] + mount[i], dp[i - 1][j]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[num][total_t];
	return 0;



	/*for (int i = 0; i < N; i++) {
		dp[0][i]=0;
		dp[i][0] = 0;
	}
	int  T, M;
	cin >> T >> M;
	for (int i = 1; i < M; i++) {
		int m, n;
		cin >> m >> n;
		dp[1][m] = n;
	}*/




}