Submission #67723237

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define all(x) (x.begin()),(x.end())
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pii;

ll n,m;
pii a[200010];
bool cmp(pii& x,pii& y){
	if(x.fs-x.sc!=y.fs-y.sc){
		return x.fs-x.sc<y.fs-y.sc;
	}
	return x.fs<y.fs;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	rep(i,1,m){
		cin>>a[i].fs>>a[i].sc;
	}
	sort(a+1,a+1+m,cmp);
	ll ans=0;
	rep(i,1,m){
		ll t=(n-a[i].fs)/(a[i].fs-a[i].sc)+(n>=a[i].fs);
		if(t>0){
			ans+=t;
			n-=t*(a[i].fs-a[i].sc);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result