stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int>pii;

const int N = 1e5+5;

struct Man{

   int a,b;

   bool operator<(const Man &rhs)const{

      return a-b>rhs.a-rhs.b;

   }

}s[N];

int n,c[N],l,ma[N],b[N];

priority_queue<pii>q;

set<pii>se;

int solve(){

  ll up=0,down=0;

  for(int i=1;i<=n;++i){

     if(up+ma[i]>=l)return i;

     up+=s[i].a-s[i].b;

     ll tmp = up-down;

     while(!q.empty()&&q.top().first>=tmp){

         int x = q.top().second;

         q.pop();

         se.erase(make_pair(s[x].b,x));

     }

     if(!se.empty()&&up+(*--se.end()).first>=l)return i;

     down+=c[i];

     if(up<=down)break;

     se.insert(make_pair(s[i].b,i));

     q.push(make_pair(s[i].a-s[i].b,i));

  }

  return -1;

}

int main() {

   scanf("%d%d",&n,&l);

   for(int i=1;i<=n;++i){

      scanf("%d%d",&s[i].a,&s[i].b);

   }

   for(int i=1;i<=n;++i)scanf("%d",&c[i]);

   sort(s+1,s+1+n);

   for(int i=n;i>=1;--i)ma[i]=max(ma[i+1],s[i].a);

   printf("%d\n",solve());

   return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;



const int maxn=1e6+5;

const int imax=1e6;

const int inf=999999999;

int en,n,a[maxn],b[maxn];

typedef long long ll;

ll tree[maxn],sum[maxn],c[maxn];



/*struct node

{

	int x,id;

//	node(int x,int id):x(x),id(id){}

}p[maxn];*/



struct node

{

    int x,id;

    node(){}

    bool operator < (const node &a) const

    {

        if(a.x==x) return id<a.id;

        return x>a.x;

    }

}p[maxn];



bool cmp(node a,node b)

{

	return a.x==b.x?a.id<b.id:a.x>b.x;

}





void build(int l,int r,int rt)

{

	if(l==r)

	{

		tree[rt]=sum[l]-c[l-1];

		return ;

	}

	int mid=(l+r)>>1;

	build(l,mid,rt*2);

	build(mid+1,r,rt*2+1);

	tree[rt]=min(tree[rt*2],tree[rt*2+1]); 

}



ll qu(int L,int R,int l,int r,int rt)

{

	if(L>R)	return inf;

	if(r<L||l>R)	return inf;

	if(l>=L&&r<=R)	return tree[rt];

	int mid=(l+r)>>1;

	int a1=inf,a2=inf;

	a1=qu(L,R,l,mid,rt*2);

	a2=qu(L,R,mid+1,r,rt*2+1);

	return min(a1,a2);

}



bool check(int i,int mid)

{

    if(i>mid) return sum[mid]+a[p[i].id]>=en;

    return sum[mid]-p[i].x+a[p[i].id]>=en;

}





int main()

{

	int ans=inf;

	c[0]=0;

	sum[0]=0;

	scanf("%d%d",&n,&en);

	for(int i=1;i<=n;++i)

	{

		scanf("%d%d",a+i,b+i);

		p[i].x=a[i]-b[i];

		p[i].id=i;

	}

	for(int i=1;i<=n;++i)

	{

		scanf("%lld",c+i);

		c[i]+=c[i-1];

	}

	sort(p+1,p+1+n,cmp);

	for(int i=1;i<=n;++i)	sum[i]=sum[i-1]+p[i].x;

	build(1,n,1);

	int gg=n;

	for(int i=1;i<=n;++i)

	{

		if(p[i].x<0)

		{

			gg=i;

			break;

		}

		

	}

	gg++;

	int num=1;

	while(sum[num]>c[num])

	{

		if(num>n)	break;

		num++;

	}

	for(int i=1;i<=n;++i)

	{

		int l=0,r=n+1;

		while(l<r)

		{

			int mid=(l+r)/2;

			if(check(i,mid))	r=mid;

			else l=mid+1;

		}

		if(r>n)	continue;

		if(r<i)

		{

			if(r<num)	ans=min(ans,r+1);

		}

		else

		if(qu(i+1,r,1,n,1)>p[i].x)	ans=min(ans,r);

	}

	if(ans==inf)	printf("-1\n");

	else printf("%d\n",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <iomanip>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <deque>

#include <set>

#include <map>

#include <utility>

#include <tuple>

#include <algorithm>

#include <cstdio>

#include <cmath>

using namespace std;



#define rep(i, n) for(int i = 0; i < (n); i++)

using ll = long long;



int main() {

  int N, M;

  cin >> N >> M;

  double p = 1/pow(2, M);

  int t = 1900*M+100*(N-M);

  double ans = 0, q = 1;

  for(int i = 1; ; i++) {

    if(t*i*q*p <= 0)

      break;

    ans += t*i*q*p;

    q *= 1-p;

  }

  cout << floor(ans+0.5) << endl;

  return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <iomanip>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <deque>

#include <set>

#include <map>

#include <utility>

#include <tuple>

#include <algorithm>

#include <cstdio>

#include <cmath>

using namespace std;



#define rep(i, n) for(int i = 0; i < (n); i++)

using ll = long long;



int main() {

  int N, M;

  cin >> N >> M;

  int x = 1900*M+100*(N-M);

  double p = 1/pow(2, M);

  /*

  かかる時間の期待値をEとする

  まず、最低でも1回は提出しないと成功しないので

    E = x + ?

  1回目で成功した場合、その後にかかる時間は0なので

    E = x + p*0 + ?

  1回目で成功しなかった場合、2回目から再度スタートする

  何回連続で失敗しても、次の回で成功する確率はpなので

  2回目からスタートして終わるまでにかかる時間の期待値もEとなる

  よって

    E = x + p*0 + (1-p)*E

  これを変形すると

  　E = x/p

  となる

  */

  cout << x/p << endl;

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)

#define all(v) v.begin(),v.end()



using namespace std;

typedef long long ll;









int main()

{

    

    

    int N,M;

    cin >> N >> M;

    

    double ans = 0;

    

    double a = (double)((N-M)*100+1900*M);

    

    double b = 1;

    rep(i,M) b/=2;

    double c = 1-b;

    

    for (int i = 1; i < 1000000; i++) {

        double j = double(i);

        ans += j*a*b;

        b *= c;

    }

    cout << ans << endl;

    

    

    return 0;

}




// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)

#define reps(i,s,n) for(int i=(s); i<(n); i++)

#define all(v) v.begin(),v.end()

#define outve(v) for(auto i : v) cout << i << " ";cout << endl

#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}

#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}

#define out(n) cout << (n) << endl

#define fi first

#define se second

#define pb push_back

#define mod 1000000007

#define infi 1900000000

#define infl 1100000000000000000

#define cyes cout << "Yes" << endl

#define cno cout << "No" << endl

#define csp << " " <<

#define outset(n) cout << fixed << setprecision(n);

using namespace std;

using ll = long long;

using ld = long double;

using vi = vector<int>;

using vvi = vector<vector<int>>;

using vs = vector<string>;

using vl = vector<ll>;

using vvl = vector<vector<ll>>;

using pii = pair<int,int>;

using pll = pair<ll,ll>;

using vvp = vector<vector<pair<int,int>>>;

template<typename T> using ve = vector<T>;

template<typename T> using pq2 = priority_queue<T>;

template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;

template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}

template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}









int main(){

    int N,M;

    cin >> N >> M;

    int a = 1;

    rep(i,M) a*=2;

    cout << a*((N-M)*100+1900*M) << endl;



    

    

    

    



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for (int i = (a); i < (b); i++)

#define REP(i,n) rep(i,0,n)



void solve() 

{

    int n,p;string s;cin>>n>>p>>s;

    int64_t ans=0;

    if(p==2||p==5){

        REP(i,n)if(!((s[i]-'0')%p))ans+=i+1;

    }else{

        map<int,int>cnt;

        cnt[0]=1;

        int64_t cur=0,ten=1;

        REP(i,n){

            (cur+=(s[n-1-i]-'0')*ten)%=p;

            ans+=cnt[cur]++;

            (ten*=10)%=p;

        }

    }

    cout<<ans<<endl;

}



int main()

{

    cin.tie(0);

	ios::sync_with_stdio(false);

    solve();

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

using namespace std;

int N,P,cur,t=1,cnt[10010],i;char S[200010];long long ans;

int main()

{

    scanf("%d%d%s",&N,&P,S);

    if(P==2||P==5){

        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;

    }else{

        cnt[0]=1;

        for(i=N-1;i>=0;i--){

            (cur+=(S[i]-'0')*t)%=P;

            ans+=cnt[cur]++;

            t=t*10%P;

        }

    }

    printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for (int i = (a); i < (b); i++)

#define REP(i,n) rep(i,0,n)



void solve() 

{

    int n,p;string s;cin>>n>>p>>s;

    int64_t ans=0;

    if(p==2||p==5){

        REP(i,n)if(!((s[i]-'0')%p))ans+=i+1;

    }else{

        map<int,int>cnt;

        cnt[0]=1;

        int cur=0,ten=1;

        REP(i,n){

            (cur+=(s[n-1-i]-'0')*ten)%=p;

            ans+=cnt[cur]++;

            (ten*=10)%=p;

        }

    }

    cout<<ans<<endl;

}



int main()

{

    cin.tie(0);

	ios::sync_with_stdio(false);

    solve();

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

using namespace std;

int N,P,cur,t=1,cnt[10010],i;char S[200010];long long ans;

int main()

{

    scanf("%d%d%s",&N,&P,S);

    if(P==2||P==5){

        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;

    }else{

        cnt[0]=1;

        for(i=N-1;i>=0;i--){

            (cur+=(S[i]-'0')*t)%=P;

            ans+=cnt[cur]++;

            t=t*10%P;

        }

    }

    printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for (int i = 0; i < (n); i++)

int main()

{

    int n,p;string s;cin>>n>>p>>s;

    int64_t ans=0;

    if(p==2||p==5){

        REP(i,n)if(!((s[i]-'0')%p))ans+=i+1;

    }else{

        map<int,int>cnt;

        cnt[0]=1;

        int cur=0,ten=1;

        REP(i,n){

            (cur+=(s[n-1-i]-'0')*ten)%=p;

            ans+=cnt[cur]++;

            (ten*=10)%=p;

        }

    }

    cout<<ans<<endl;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

using namespace std;

int N,P,cur,t=1,cnt[10010],i;char S[200010];long long ans;

int main()

{

    scanf("%d%d%s",&N,&P,S);

    if(P==2||P==5){

        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;

    }else{

        cnt[0]=1;

        for(i=N-1;i>=0;i--){

            (cur+=(S[i]-'0')*t)%=P;

            ans+=cnt[cur]++;

            t=t*10%P;

        }

    }

    printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

long N,P,ans,cur,t=1,cnt[10010],i;string S;

int main()

{

    cin>>N>>P>>S;

    if(P==2||P==5){

        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;

    }else{

        cnt[0]=1;

        for(i=N-1;i>=0;i--){

            (cur+=(S[i]-'0')*t)%=P;

            ans+=cnt[cur]++;

            t=t*10%P;

        }

    }

    cout<<ans;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

using namespace std;

int N,P,cur,t=1,cnt[10010],i;char S[200010];long long ans;

int main()

{

    scanf("%d%d%s",&N,&P,S);

    if(P==2||P==5){

        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;

    }else{

        cnt[0]=1;

        for(i=N-1;i>=0;i--){

            (cur+=(S[i]-'0')*t)%=P;

            ans+=cnt[cur]++;

            t=t*10%P;

        }

    }

    printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

int N,P,cur,t=1,cnt[10010],i;char S[200010];int64_t ans;

int main()

{

    scanf("%d%d%s",&N,&P,S);

    if(P==2||P==5){

        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;

    }else{

        cnt[0]=1;

        for(i=N-1;i>=0;i--){

            (cur+=(S[i]-'0')*t)%=P;

            ans+=cnt[cur]++;

            t=t*10%P;

        }

    }

    printf("%lld",ans);

}

// Optimized solution to the same problem (faster):
#include <cstdio>

using namespace std;

int N,P,cur,t=1,cnt[10010],i;char S[200010];long long ans;

int main()

{

    scanf("%d%d%s",&N,&P,S);

    if(P==2||P==5){

        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;

    }else{

        cnt[0]=1;

        for(i=N-1;i>=0;i--){

            (cur+=(S[i]-'0')*t)%=P;

            ans+=cnt[cur]++;

            t=t*10%P;

        }

    }

    printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



typedef long long int LLI;



// #define debug



bool check(LLI k, LLI a, LLI b, LLI x, LLI y) {

    return k*x >= a && k*y >= b;

}





int main() { 

    int n, x, y;

    while (cin >> n) {

        LLI a = 0, b = 0, lo, hi, mi;

        cin >> a >> b;

        for (int i = 1; i < n; ++i) {

            cin >> x >> y;

            lo = 1, hi = min(1e18/x, 1e18/y);

            while (lo < hi) {

                mi = (lo+hi)>>1;

                if (check(mi, a, b, x, y)) hi = mi;

                else lo = mi+1;

            }

            a = x*lo;

            b = y*lo;

#ifdef debug

            cout << a << " " << b << "\n";

#endif

        }

        cout << a+b << "\n";

    }



    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 1000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

LL A[MAXN+5],B[MAXN+5];

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%lld %lld",&A[i],&B[i]);

	LL k;

	for(int i=2;i<=n;i++)

	{

		k=-1LL;

		if(A[i]>=A[i-1]&&B[i]>=B[i-1])

			continue;

		LL L=1LL,R=INF,mid;

		while(L+1<R)

		{

			mid=(L-R)/2LL+R;

			if((A[i]*mid>=A[i-1]&&B[i]*mid>=B[i-1])||(A[i]*mid<=0||B[i]*mid<=0))

				R=mid;

			else

				L=mid;

		}

		k=R;

		A[i]*=k;

		B[i]*=k;

	}

	printf("%lld\n",A[n]+B[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

 

using namespace std;

 

typedef long long ll;

 

ll t[1005];

ll a[1005];

 

int main(){

    //freopen("c3.in", "r", stdin);

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {

        scanf("%lli %lli", &t[i], &a[i]);

    }

    ll currentT = 1, currentA = 1;

    for (int i = 0; i < n; ++i) {

        ll multiT = (currentT - 1LL) / t[i] + 1LL;

        ll multiA = (currentA - 1LL) / a[i] + 1LL;

        ll multi = max(multiT, multiA);

        currentT = t[i] * multi;

        currentA = a[i] * multi;

        //printf("%d %lli %lli %lli %lli\n", i, multiT, multiA, currentT, currentA);

    }

    printf("%lli\n", currentT + currentA);

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 1000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

LL A[MAXN+5],B[MAXN+5];

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%lld %lld",&A[i],&B[i]);

	LL k;

	for(int i=2;i<=n;i++)

	{

		k=-1LL;

		if(A[i]>=A[i-1]&&B[i]>=B[i-1])

			continue;

		LL L=1LL,R=INF,mid;

		while(L+1<R)

		{

			mid=(L-R)/2LL+R;

			if((A[i]*mid>=A[i-1]&&B[i]*mid>=B[i-1])||(A[i]*mid<=0||B[i]*mid<=0))

				R=mid;

			else

				L=mid;

		}

		k=R;

		A[i]*=k;

		B[i]*=k;

	}

	printf("%lld\n",A[n]+B[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <algorithm>

#include <iostream>

#include <iterator>

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;





#ifdef LOCAL

#define DEBUGMSG()                                                              \

{                                                                               \

    cerr << "[调试 @" << __PRETTY_FUNCTION__ << ":" << __LINE__ << "]" ;        \

}

#define DEBUGVAR(x)                                                             \

{                                                                               \

    cerr << "[调试 @" << __PRETTY_FUNCTION__ << ":" << __LINE__ << "]:" ;       \

    cerr << "([" << typeid(x).name() << "]" << #x << ")" << x << endl ;         \

}

#define DEBUGARR(l, r)                                                          \

{                                                                               \

    cerr << "[调试 @" << __PRETTY_FUNCTION__ << ":" << __LINE__ << "]:" ;       \

    copy(l, r, ostream_iterator<decltype(*l)>(cerr, " "));                      \

    cerr << endl ;                                                              \

}

#else

#define DEBUGMSG()

#define DEBUGVAR(x)

#define DEBUGARR(l, r)

#endif // LOCAL



using i64 = long long;



int N;

vector <int> A, T;



int main()

{



    cin >> N ;



    i64 a, t;

    i64 ansA, ansT;



    cin >> ansA >> ansT;

    for(int i = 1; i < N; i++)

    {

        cin >> a >> t;

        if(ansA % a)

            ansA = (ansA/a + 1) * a;



        if(ansT <= ansA / a * t)

            ansT = ansA / a * t;

        else

        {

            if(ansT % t)

                ansT = (ansT/t + 1) * t;

            ansA = ansT / t * a;

        }





    }

    cout << ansA + ansT << endl ;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 1000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

LL A[MAXN+5],B[MAXN+5];

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%lld %lld",&A[i],&B[i]);

	LL k;

	for(int i=2;i<=n;i++)

	{

		k=-1LL;

		if(A[i]>=A[i-1]&&B[i]>=B[i-1])

			continue;

		LL L=1LL,R=INF,mid;

		while(L+1<R)

		{

			mid=(L-R)/2LL+R;

			if((A[i]*mid>=A[i-1]&&B[i]*mid>=B[i-1])||(A[i]*mid<=0||B[i]*mid<=0))

				R=mid;

			else

				L=mid;

		}

		k=R;

		A[i]*=k;

		B[i]*=k;

	}

	printf("%lld\n",A[n]+B[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>



using namespace std;



typedef unsigned long long ull;



ull div_ceil(ull a, ull b)

{

    return (a + b - 1) / b;

}



int main()

{

    int n; cin >> n;

    ull x, y;

    cin >> x >> y;

    for (int i = 1; i < n; ++i) {

        ull p, q;

        cin >> p >> q;

        ull n = max(div_ceil(x, p), div_ceil(y, q));

        x = n * p;

        y = n * q;

    }

    cout << x + y << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>  

#include<string.h>  

#include<math.h>  

#include<algorithm>  

using namespace std;  

int main()  

{  

    long long n, a, b, x1, x2;  

    scanf("%lld%lld%lld", &n, &a, &b);  

    x1=a;x2=b;  

    for(int i=0;i<n-1;i++)  

    {  

        scanf("%lld%lld", &a, &b);  

        long long temp=x1/a;  

        if(x1%a!=0)  

            temp++;  

        long long temp2=x2/b;  

        if(x2%b!=0)  

            temp2++;  

        long long m=max(temp, temp2);  

        x1=a*m;x2=b*m;  

    }  

    printf("%lld\n", x1+x2);  

    return 0;  

}   

       	

  

 

// Fastest known solution for this problem:
// Original C++ solution (slower):
	#include <iostream>

	#include <vector>

	#include <set>

	#include <cmath>



	using namespace std;



	int main() {

		long long int realt = 1, reala = 1;

		int n;

		cin >> n;

		for(int i = 0; i < n; i++) {

			long long int t, a;

			cin >> t >> a;

			if(reala > a || realt > t) {

				long double mula = ((long double)reala)/a;

				long double mult = ((long double)realt)/t;

				if(mula > mult) {

					long long int increase = (long long int)ceil(mula);

					realt = t*increase;

					reala = a*increase;

				}

				else {

					long long int increase = (long long int)ceil(mult);

					realt = t*increase;

					reala = a*increase;

				}

			}

			else {

				realt = t;

				reala = a;

			}

		}

		long long int ans = realt + reala;

		cout << ans << endl;

	}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long LL;

inline LL gcd(LL a,LL b)

{

	return !b?a:gcd(b,a%b);

}



int main()

{

	int n;

	scanf("%d",&n);

	

	LL a,b,A=1,B=1;

	LL G;

	for(int i=1;i<=n;i++)

	{

		scanf("%lld %lld",&a,&b);

		if(a>A && b>B) A=a,B=b;

		else

		{

			G=max((A/a)+(A%a?1:0),B/b+(B%b?1:0));

			A=a*G,B=b*G;

		}

	}

	

	printf("%lld\n",A+B);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cmath>

using namespace std;

long long N,T,A,ans,a_ans=1,b_ans=1,ratio;

int main(){

	cin>>N;

	for(int i=1;i<=N;++i){

		cin>>T>>A;

		ratio=max(a_ans/T,b_ans/A);

		while(ratio*T<a_ans || ratio*A<b_ans)

			ratio++;

		a_ans=ratio*T;

		b_ans=ratio*A;

		/*

		if(ratio<T*1.0/A){

			while(ratio!=T*1.0/A) {

				++T;

				ans=

			}

		}

		else if(ratio>T*1.0/A){

			while(ratio!=T*1.0/A) {

				++T;

				ans=T+A;

			}

		}

		ratio=T*1.0/A;

		*/

	}

	cout<<a_ans+b_ans<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long LL;

inline LL gcd(LL a,LL b)

{

	return !b?a:gcd(b,a%b);

}



int main()

{

	int n;

	scanf("%d",&n);

	

	LL a,b,A=1,B=1;

	LL G;

	for(int i=1;i<=n;i++)

	{

		scanf("%lld %lld",&a,&b);

		if(a>A && b>B) A=a,B=b;

		else

		{

			G=max((A/a)+(A%a?1:0),B/b+(B%b?1:0));

			A=a*G,B=b*G;

		}

	}

	

	printf("%lld\n",A+B);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>



typedef long long LL;



LL ceil(LL a, LL b) {

    if (a % b == 0) return a / b;

    return 1 + (a / b);

}



int main() {

    LL A = 1, B = 1;

    int t; std::cin >> t;

    while (t--) {

        LL a, b; std::cin >> a >> b;

        LL c = ceil(A, a);

        LL d = ceil(B, b);

        LL e = std::max(c, d);

        A = a * e;

        B = b * e;

    }

    std::cout << A + B << std::endl;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define N 100010

using namespace std;

int main()

{

    int a,b,n;

    long long x1,x2,sum,ans,m;

    scanf("%d",&n);

    scanf("%d %d",&a,&b);

    x1=a,x2=b;

    for(int i=0;i<n-1;i++)

    {

        scanf("%d %d",&a,&b);

        sum=x1/a;

        if(x1%a!=0)

            sum++;

        ans=x2/b;

        if(x2%b!=0)

            ans++;

        m=max(sum,ans);

        x1=a*m,x2=b*m;

    }

    printf("%lld",x1+x2);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll inf=1e18;

ll a[1010],t[1010],ans1,ans2,ans,l,r,mid;

int n;

int main()

{

	ios::sync_with_stdio(0);

	cin>>n;

	for(int i=1;i<=n;i++)

		cin>>t[i]>>a[i];

	ans1=t[1],ans2=a[1];

	for(int i=2;i<=n;i++)

	{

		if(ans1*a[i]==ans2*t[i])continue;

		else 

		{

			l=1;r=inf/max(a[i],t[i])+1;

			ans=r;

			while(l<=r)

			{

				mid=(l+r)>>1;

				if(mid*t[i]>=ans1&&mid*a[i]>=ans2)ans=mid,r=mid-1;

				else l=mid+1;

			}

			ans1=ans*t[i],ans2=ans*a[i];

		}

	}

	cout<<ans1+ans2<<endl;	

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define N 100010

using namespace std;

int main()

{

    int a,b,n;

    long long x1,x2,sum,ans,m;

    scanf("%d",&n);

    scanf("%d %d",&a,&b);

    x1=a,x2=b;

    for(int i=0;i<n-1;i++)

    {

        scanf("%d %d",&a,&b);

        sum=x1/a;

        if(x1%a!=0)

            sum++;

        ans=x2/b;

        if(x2%b!=0)

            ans++;

        m=max(sum,ans);

        x1=a*m,x2=b*m;

    }

    printf("%lld",x1+x2);

    return 0;

}


// Fastest known solution for this problem: