众所周知，这道题是背包dp题，我会，但是我就不这么写，我偏要用模拟退火

#include <bits/stdc++.h>

#define IS std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define OS std::cout.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define srnd srand((unsigned int)time(0))
#define rnd rand()
#define save(x) std::fixed << std::setprecision(x)
#define set_0(x) memset(x, 0, sizeof(x))
#define set_false(x) memset(x, false, sizeof(x))
#define set_true(x) memset(x, true, sizeof(x))
#define set_nega1(x) memset(x, -1, sizeof(x))
#define set_Iinf(x) memset(x, 0x7f, sizeof(x))
#define set_Finf(x) memset(x, 7e4, sizeof(x));
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define low_bit(x) (x & (-x))
#define __DEBUG__ puts("DEBUG")

using namespace std;

int k, n, need[105], value[105], sum_T = 0, sum_V = 0, ans = 0;
constexpr double Tk = 0.99889, min_T = 1e-18, start_T = 3726, solve_T = 0.95;

struct Func {
    
    double T;
    bitset <105> can_pick, vis;
    
    void Init(void) {
        
        scanf("%d%d",&k,&n);
        
        for(int i = 0; i < n; ++i) {
            
            scanf("%d%d",&need[i],&value[i]);
            
            if(need[i] <= k) {
                
                can_pick[i] = true;
            }
        }
        
        srnd;
        
        return;
    }
    
    void Anneal(void) {
        
        while(T >= min_T) {
            
            ans = max(ans, sum_V);
            
            int search = rnd % n;
            
            if(can_pick[search] == false) {
                
                continue;
            }
            
            int del = (value[search] - need[search]) << 1;
            
            if(vis[search] == true) {
                
                del = -del;
            }
            
            if(del > 0 || exp(del / T) > (double)rnd / RAND_MAX) {
                
                if(vis[search] == true) {
                    
                    vis[search] = false;
                    
                    sum_T -= need[search];
                    sum_V -= value[search];
                }
                
                else {
                    
                    if(sum_T + need[search] > k) {
                        
                        continue;
                    }
                    
                    vis[search] = true;
                    
                    sum_T += need[search];
                    sum_V += value[search];
                }
            }
            
            T *= Tk;
        }
        
        return;
    }

    void Solve(void) {
        
        while((double)clock() / CLOCKS_PER_SEC <= solve_T) {
            
            T = start_T;
            Anneal();
        }
        
        return;
    }
    
} CJR;

signed main() {
    
    CJR.Init();
    CJR.Solve();
    
    printf("%d",ans);
    
    return 0;
}