Submission #3677227

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define REP0(i,n) for(ll i=0;i<(n);++i)
#define REP1(i,n) for(ll i=1;i<=(n);++i)
#define ALL(c) (c).begin(),(c).end()
typedef long long ll;
typedef pair<ll,ll> P;
int main(){
	ll a[100],b[100],n,s=0;
	cin >> n;
	REP0(i,n){
		cin >> a[i] >> b[i];
		s+=a[i];
	}
	ll ans=10000000000000000;
	REP0(i,s){
		P mod[100]={};
		ll c[100]={},left=i;
		REP0(j,n){
			mod[j]=P(-(a[j]*i)%s,j);
			left-=(a[j]*i)/s;
			c[j]=(a[j]*i)/s;
		}
		sort(mod,mod+n);
		REP0(j,left) c[mod[j].second]++;
		ll dif=-1;
		REP0(j,n) dif=max(dif,(b[j]-c[j]+a[j]-1)/a[j]);
		ans=min(ans,dif*s+i);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result