Submission #67730782

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)
#define pb emplace_back
#define fi first
#define se second
using vi = vector<int>;
using pi = pair<int,int>;

template<typename T0, typename T1> bool chmin(T0 &x, const T1 &y){
	if(y < x){x = y; return true;} return false;
}
template<typename T0, typename T1> bool chmax(T0 &x, const T1 &y){
	if(y > x){x = y; return true;} return false;
}

template<typename T> void debug(char *s, T x){
	cerr<< s <<" = "<< x <<endl;
}
template<typename T, typename ...Ar> void debug(char *s, T x, Ar... y){
	int dep = 0;
	while(!(dep == 0 && *s == ',')){
		if(*s == '(') dep++;
		if(*s == ')') dep--;
		cerr << *s++;
	}
	cerr <<" = "<< x <<",";
	debug(s + 1, y...);
}
#define gdb(...) debug((char*)#__VA_ARGS__, __VA_ARGS__)

constexpr int V = 305, T = 1e6;

signed main(){
	#ifdef LOCAL
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<pi> c(m);
	vi mx(V);
	for(auto &[a, b]:c){
		cin >> a >> b;
		chmax(mx[a], b);
	}
	vi f(T);
	rep(i, 1, T - 1){
		rep(j, 1, min(V - 1, i)){
			chmax(f[i], f[i - j + mx[j]] + j);
		}
	}
	int ans = 0;
	rep(i, 1, V - 1){
		int k = i - mx[i];
		int d = max(0ll, n - T + 1);
		int c = (d + k - 1) / k;
		chmax(ans, c * i + f[n - c * k]);
	}
	cout << ans <<'\n';
}

Submission Info

Judge Result