//https://www.luogu.com.cn/problem/P1616
//完全背包問題
#include<bits/stdc++.h>
using namespace std;
int T,m;
long long t[10001];
long long value[10001];
//long long dp[10001][10001];
long long dp[10000001];
int main()
{
? ?cin>>T>>m;
? ?for(int i=1;i<=m;i++)
? ?{
? ? ? ?cin>>t[i];
? ? ? ?cin>>value[i];
? ?}
? ?//背包初始化化
// ? ?for(int i=1;i<=m;i++)
// ? ? ? ?dp[0][i]=0;
// ? ?for(int i=1;i<=m;i++)
// ? ? ? ?for(int j=1;j<=T;j++)
// ? ? ? ?{
// ? ? ? ? ? ?if(j>=t[i])//注意一定要有等號(hào)啊-----等于也是可以采的
// ? ? ? ? ? ?{
// ? ? ? ? ? ? ? ?dp[i][j]=max(dp[i][j-t[i]]+value[i],dp[i-1][j]);
// ? ? ? ? ? ?}
// ? ? ? ? ? ?else
// ? ? ? ? ? ? ? ?dp[i][j]=dp[i-1][j];
// ? ? ? ?}
// ? ?cout<<dp[m][T];
// ? for(int i=1;i<=m;i++)
// ? {
// ? ? ? for (int j = 1; j <= T; j++)
// ? ? ? {
// ? ? ? ? ? printf("%d ", dp[i][j]);
// ? ? ? }
// ? ? ? printf("\n");
// ? }
// ? ? ? ?return 0;
? ? ? ?//采用二維數(shù)組的完全背包已經(jīng)超出內(nèi)存限制了，故使用一維滾動(dòng)數(shù)組實(shí)現(xiàn)背包
? ? ? ?//初始化
? ? ? ?for(int i=1;i<=m;i++)
? ? ? ? ? ?dp[i]=0;
? ? ? ?for(int i=1;i<=m;i++)
? ? ? ? ? ?for(int j=1;j<=T;j++)//完全背包一維情況要正序枚舉背包容量已提供充足的信息
? ? ? ? ? ?{
? ? ? ? ? ? ? ?if(j>=t[i])
? ? ? ? ? ? ? ? ? ?dp[j]=max(dp[j],dp[j-t[i]]+value[i]);
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ?dp[j]=dp[j];
? ? ? ? ? ?}
? ? ? ?cout<<dp[T];
? ? ? ? ? ?return 0;
}