https://www.acwing.com/problem/content/428/

#include<bits/stdc++.h>
using namespace std;
const int N=30000+10;
int v[N],w[N];
int f[30][N];

int main(){
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=m;i++){
      scanf("%d%d",&v[i],&w[i]);
    //  k[i]=v[j]*w[j];
    }

    f[1][v[1]]=v[1]*w[1];

    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(v[i]<=j){
            f[i][j]=max(f[i-1][j-v[i]]+v[i]*w[i],f[i-1][j]);
            }
            else{
                f[i][j]=max(f[i-1][j],f[i][j]);
            }
        }
    }

  cout<<f[m][n]<<endl;
    return 0;
}