01背包模型

#include <iostream>
using namespace std;
const int N = 3 * 1E4 + 10;
typedef long long ll;
ll a[N], v[N], f[N];
int main(){
    int m, n;   cin >> m >> n;
    for(int i = 0; i < n; i ++ ){
        cin >> a[i] >> v[i];
        v[i] *= a[i];
    }
    for(int i = 0; i < n; i ++ ){
        for(int j = m; j >= 1; j -- ){
            if(a[i] > j)    continue;
            f[j] = max(f[j], f[j - a[i]] + v[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}