akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(void){
    ll n,m;cin>>n>>m;
    combination c(1e6);
    vector<mint> fact(1e6,1);
    rep(i,1e6-1) fact[i+1]=fact[i]*(i+1);
    mint res=(fact[m]/fact[m-n])*(fact[m]/fact[m-n]);
    rep(k,n+1){
        if(k==0)continue;
        mint buf=c(n,k)*(fact[m]/fact[m-n])*(fact[m-k]/fact[m-n]);
        if(k%2==0)res+=buf;
        else res-=buf;
    }
    cout<<res.x<<endl;
}

Measured memory_bytes: 26752
#include <iostream>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<21)

int main(){
	int n;
	cin >> n;
	while(n--){
		int pos = 0 , l = 0 , r = 0;
		map<int,char> g;
		string s;
		cin >> s;
		for(int i=0;i<s.size();i+=3){
			g[pos] = s[i];
			if(i == s.size()-1)break;
			if(s[i+1] == '<')pos--;
			else pos++;
		}
		for(map<int,char>::iterator it = g.begin(); it != g.end();++it)
			cout << it->second ;
		cout << endl;
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int main(){
  ll n,inp,p; vector<ll> v; cin >> n;
  
  for(int i=0; i<5; i++){
    cin >> inp;
    v.push_back(inp);
  }
  
  ll min = *min_element(begin(v), end(v));
  ll q = n/min; int r;
  if(n%min!=0){r++;}
  ll tp = q + r + 4;
  cout << tp;
  
  return 0;
}

Measured memory_bytes: 256
A, B, C = map(int, input().strip().split())
K = int(input())

while A >= B and K > 0:
    B = B * 2
    K -= 1

while B>=C and K>0:
    C=C*2
    K-=1

if A<B and B<C :
    print("Yes")
else:
    print("No")




Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int a,b,c;
  cin>>a>>b>>c;
  cout<<min(b/a,c)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())
const int N = 1005;
char color[205];
int n;
int perm[205] , inv[205];
int cnt = 0;
bool query(vector<int> v)
{
	cnt++;
	if(cnt == 211)
	{
		set<int> s;
		for(int i = 0; i < 10000 * 10000; i++)
			s.insert(i);
		cout << *s.begin() << endl;
	}
	cout << "?";
	for(auto x : v)
		cout << " " << perm[x] + 1;
	cout << endl;
	string resp;
	cin >> resp;
	return resp == "Red";
}
int f(int x)
{
	vector<int> v;
	for(int i = 0; i < n; i++)
		v.pb(i + x);
	return query(v);
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	srand(time(NULL) + 47);
	cin >> n;
	for(int i = 0; i < 2 * n; i++)
	{
		perm[i] = i;
	}
	for(int i = 0; i < 2 * n; i++)
		inv[perm[i]] = i;
	vector<int> v;
	for(int i = 0; i < n; i++)
		v.pb(i);
	int resp = query(v);
	bool was = false;
	
	int L = 0 , R = n;
	while(R - L > 1)
	{
		int M = (L + R) / 2;
		
		if(f(M) == resp)
			L = M;
		else
			R = M;
	}
	
	vector<int> v2;
	for(int j = L + 1; j < L + n; j++)
		v2.pb(j);
	v2.pb(-1);
	int cntR = 0 , cntB = 0;
	for(int j = 0; j < 2 * n; j++)
	{
		if(j >= L + 1 && j < L + n)
			continue;

		v2.back() = j;
		int resp3 = query(v2);
		color[j] = resp3 ? 'R' : 'B';
	}
	v2.clear();
	for(int j = 0; j < 2 * n; j++)
	{
		if(color[j] == 'R' && cntR < n / 2)
		{
			cntR++;
			v2.pb(j);
		}
		if(color[j] == 'B' && cntB < n / 2)
		{
			cntB++;
			v2.pb(j);
		}
	}
	
	v2.pb(-1);
	
	for(int j = L + 1; j < L + n; j++)
	{
		v2.back() = j;
		int resp3 = query(v2);
		color[j] = resp3 ? 'R' : 'B';	
	}
		
	cout << "! ";
	for(int i = 0; i < 2 * n; i++)
		cout << color[inv[i]];
	cout << endl;
	
}


Measured memory_bytes: 724
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

int upperBound(lli arr[], int lo, int hi, lli target)
{
  while (lo < hi)
  {
    int mid = (lo + hi + 1) >> 1;
    if (arr[mid] <= target) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

int main()
{
  int n, m; lli k;
  while (scanf("%d %d %lld", &n, &m, &k) != EOF)
  {
    lli a[n], b[m];
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for (int i = 0; i < m; i++) scanf("%lld", &b[i]);

    lli aa[n + 1], bb[m + 1];
    aa[0] = bb[0] = 0;
    for (int i = 0; i < n; i++) aa[i + 1] = aa[i] + a[i];
    for (int i = 0; i < m; i++) bb[i + 1] = bb[i] + b[i];

    int ans = 0;
    for (int i = 0; i <= n; i++)
      if (aa[i] < k)
        ans = max(ans, i + upperBound(bb, 0, m, k - aa[i]));
    for (int i = 0; i <= m; i++)
      if (bb[i] < k)
        ans = max(ans, i + upperBound(aa, 0, n, k - bb[i]));

    printf("%d\n", ans);
  }
  return 0;
}

Measured memory_bytes: 10072
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int INF = 1<<29;

int dp[150][10][77];
int stones[150][10][2];
int col[150];

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  while (true) {
    int N, M;
    cin >> N >> M;
    if (N == 0 && M == 0) break;
  
    REP(i, N) {
      cin >> col[i];
      REP(j, col[i]) {
	cin >> stones[i][j][0] >> stones[i][j][1];
      }
    }

    REP(i, N) REP(j, col[i]) REP(k, M+1) dp[i][j][k] = INF;
    REP(j, col[0]) dp[0][j][0] = 0;
    REP(j, col[1]) dp[1][j][1] = 0;
    REP(i, N-1) {
      REP(j, col[i]) {
	int x_now = stones[i][j][0], d_now = stones[i][j][1];
	REP(m, M+1) {
	  if (dp[i][j][m] == INF) continue;
	  REP(k, col[i+1]) {
	    dp[i+1][k][m] = min(dp[i+1][k][m], dp[i][j][m] + (d_now + stones[i+1][k][1]) * abs(x_now - stones[i+1][k][0]));
	  }
	  if (i < N-2 && m < M) {
	    REP(k, col[i+2]) {
	      dp[i+2][k][m+1] = min(dp[i+2][k][m+1], dp[i][j][m] + (d_now + stones[i+2][k][1]) * abs(x_now - stones[i+2][k][0]));
	    }
	  }
	}
      }
    }

    int ans = INF;
    REP(j, col[N-1]) REP(m, M+1) ans = min(ans, dp[N-1][j][m]);
    REP(j, col[N-2]) REP(m, M) ans = min(ans, dp[N-2][j][m]);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1656
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()


ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
int main(){
  ll x ;
  cin >> x;
  for(ll a=-300;a<=300;a++){
    for(ll b=-300;b<=300;b++){
      if(a*a*a*a*a-b*b*b*b*b==x){
        cout << a << " " << b <<endl;
        return 0;
      }
    }
  }
  return 0;
}



Measured memory_bytes: 3532
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mod 1000000007ll
const ll maxn = 9e18;
using namespace std;

void solve() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	int dx = abs(sx - tx), dy = abs(sy - ty);
	cout << string(dx, 'R') << string(dy, 'U') << string(dx, 'L') << string(dy, 'D');
	cout << "D";
	cout << string(dx + 1, 'R') << string(dy + 1, 'U') << "L";
	cout << "U";
	cout << string(dx + 1, 'L') << string(dy + 1, 'D') << "R" << endl;
}

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout.precision(35);
	solve();
	return 0;
	}


Measured memory_bytes: 3512
#include <iostream>
using namespace std;
void ABC70(void);
void ABC71(void);
void ABC72(void);
void ABC73(void);
void ABC75(void);
void ABC77(void);
void ABC78(void);
void ABC79(void);

int main(void){
    ABC79();
}

void ABC79(void){
    int n,a,b,c,d;
    cin>>n;
    a=n/1000;
    b=(n/100)%10;
    c=(n/10)%10;
    d=n%10;
    if((a==b||c==d)&&(b==c))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> h(N);
    for (int i=0; i<N; i++) { cin >> h[i]; }

    sort(h.begin(), h.end());
    int l = 0, r = K-1;
    int diff = h[r] - h[l];
    while(r != N) {
        if (diff > h[r] - h[l]) diff = h[r] - h[l];
        l++;
        r++;
    }
    cout << diff << endl;
    return 0;
}

Measured memory_bytes: 640
package main

import (
	"fmt"
)

func main() {
	var age, price int
	fmt.Scan(&age, &price)

	if age >= 13 {
		fmt.Println(price)
	} else if 6 <= age {
		fmt.Println(price / 2)
	} else {
		fmt.Println(0)
	}

}


Measured memory_bytes: 512
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
	int N; cin >> N;
	int M; cin >> M;
	bool adj[N][N]; F0R(i, N) F0R(j, N) adj[i][j] = false;
	
	F0R(i, M) {
		int A, B; cin >> A >> B; A--; B--;
		adj[A][B] = true;
	}
	
	ld E[N], P[N]; F0R(i, N) E[i] = 0, P[i] = 0;
	
	E[N-1] = 0; P[0] = 1;
	int deg[N]; F0R(i, N) {
		deg[i] = 0;
		F0R(j, N) if (adj[i][j]) deg[i]++;
	}
	
	F0R(i, N) {
		FOR(j, i+1, N) {
			if (!adj[i][j]) continue;
			P[j] += P[i] / deg[i];
		}
	}
	
	F0Rd(i, N) {
		F0R(j, i) {
			if (!adj[j][i]) continue;
			E[j] += (E[i] + 1) / deg[j];
		}
	}
	
	/*F0R(i, N) {
		cout << E[i] << " ";
	}
	cout << endl;
	F0R(i, N) {
		cout << P[i] << " ";
	}
	cout << endl;*/
	
	ld ans = E[0];
	F0R(i, N) {
		if (deg[i] == 1) continue;
		FOR(j, i+1, N) {
			if (!adj[i][j]) continue;
			ld val = E[0]; val -= E[i] * P[i];
			ld curE = E[i];
			curE -= 1;
			curE -= E[j] / deg[i];
			curE *= deg[i]; 
			curE /= (deg[i]-1);
			curE += 1;
			//cout << curE << " " << i << " " << j << endl;
			val += curE * P[i];
			//cout << val << " " << E[i] << " " << P[i] << endl;
			ans = min(ans, val);
		}
	}
	
	cout << setprecision(20) << ans << endl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int N;
int dp[62][3];

inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}

signed main(){
    cin>>N;
    dp[60][0]=1;
    for(int i=59;i>=0;i--){
        for(int j=0;j<=2;j++){
            for(int a=0;a<=2;a++){
                int nj=j*2+(N>>i&1)-a;
                if(nj<0)continue;
                if(nj>2)nj=2;

                add(dp[i][nj],dp[i+1][j]);
            }
        }
    }

    int ans=0;
    rep(i,3)add(ans,dp[0][i]);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;string s;map<char,long>d;
int main(){
    cin>>n;
    while(n--)cin>>s,d[s[0]]++;
    long m=d['M'],a=d['A'],r=d['R'],c=d['C'],h=d['H'];
    cout<<m*a*(r+c+h)+(m+a+r)*c*h+(m+a)*r*(c+h);
}

Measured memory_bytes: 256
n=int(input())
a=[input() for i in range(n)]
b=set(a)
c=0
if len(a)!=len(b):print("No")
else:
  for x in range(n-1):
     if a[x][len(a[x])-1]!=a[x+1][0]:c+=1
     else:pass
  if c>0:print("No")
  else:print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 100005

int n,m;
ll h[MAXN];
bool ok[MAXN];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>h[i]; ok[i]=1;
	}
	for(int i=0;i<m;i++){
		int u,v; cin>>u>>v; u--; v--;
		if(h[u]<=h[v]) ok[u]=0;
		if(h[u]>=h[v]) ok[v]=0;
	}
	
	int cnt=0;
	for(int i=0;i<n;i++){
		if(ok[i]) cnt++;
	}
	
	cout<<cnt<<'\n';
	
	return 0;
}


Measured memory_bytes: 4520
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  if ((A==B) && (B!=C)) {
    cout << "Yes" << endl;
  } else if ((A==C) && (B!=C))  {
    cout << "Yes" << endl;
  } else if ((B==C) && (A!=B))  {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using i64 = long long;

int main() {
    int k;
    std::string s;
    std::cin >> k >> s;
    if (s.size() <= k) std::cout << s << std::endl;
    else std::cout << s.substr(0, k) << "..." << std::endl;

    return 0;
}


Measured memory_bytes: 3560
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MOD = (int)1e9 + 7;

struct mat {
	int arr[50][50];

	mat() {
		for(int i=0; i<50; i++) {
			for(int j=0; j<50; j++) {
				arr[i][j] = 0;
			}
		}
	}
};

int n, k;
mat I, B;

mat mul(mat a, mat b) {
	mat res;
	for(int i=0; i<50; i++) {
		for(int j=0; j<50; j++) {
			int x = 0;
			for(int k=0; k<50; k++) {
				x = (x + (a.arr[i][k] * b.arr[k][j]) % MOD) % MOD;
			}
			res.arr[i][j] = x;
		}
	}
	return res;
}

mat modPow(mat b, int p) {
	mat res = I;
	while(p) {
		if(p&1) res = mul(res, b);
		b = mul(b,b);
		p >>= 1;
	}
	return res;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;
	for(int i=0; i<50; i++)
        I.arr[i][i] = 1;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cin >> B.arr[i][j];
		}
	}
	B = modPow(B,k);
	int ans = 0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			ans = (ans + B.arr[i][j]) % MOD;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 512
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate

    N = int(readline())
    A = list(map(int, readline().split()))
    acc = list(accumulate(A))
    S = sum(A)

    ans = INF
    for first in acc:
        second = S - first
        ans = min(ans, abs(first - second))

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 106768
#include<stdio.h>
int main() {
	int xa, xb, ya, yb,xinc,yinc;
	scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
	xinc = xb - xa;
	yinc = yb - ya;
		printf("%d %d %d %d", xb - yinc, yb + xinc, xa - yinc, ya + xinc);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long x=7,k,i,j;
	cin>>k;
	for(i=1;i<k+10;i++){
		if(x%k==0){
			cout<<i<<endl;
			return 0;
		}
		x%=k;
		x=x*10+7;
	}
	cout<<-1<<endl;
	return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

int dp[114][114514];

int main(){
        int N,W;
        cin>>N>>W;
        vector<int>v(N),w(N);
        for(int i=0;i<N;i++)cin>>v[i]>>w[i];
        for(int i=0;i<N;i++){
                for(int j=0;j<=W;j++){
                        if(j>=w[i])dp[i+1][j]=max(dp[i+1][j-w[i]]+v[i],dp[i][j]);
                        else dp[i+1][j]=dp[i][j];
                }
        }
        cout<<dp[N][W]<<endl;
}



Measured memory_bytes: 7392
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
const ll mod = 1000000007;

int main() {
    int n,d;
    cin >> n >> d;
    int point[n][d];
    rep(i,n) rep(j,d) cin >> point[i][j];
    int p[100000];
    rep(i,100000) p[i] = 0;
    rep(i,160) p[i*i] = 1;
    int ans = 0;
    rep(i,n) {
        for(int j = i+1; j < n; j++) {
            int dist = 0;
            for (int k = 0; k < d;  k++) {
                dist += (point[i][k] - point[j][k])*(point[i][k] - point[j][k]);
            }
            if (p[dist]) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(s,i, n) for (int i = (int)s; i < (int)(n); i++)
#define pb push_back
typedef long long ll;
  
int main(){
    int n;
    cin>>n;
    vector<int> s(n,0);
    int min=100000;
    rep(i,n){
        int a;
        cin>>a;
        s[i]=(i==0)?a:s[i-1]+a;
    }
    rep(i,n-1){
        if(abs(s[i]-(s[n-1]-s[i]))<min)min=abs(s[i]-(s[n-1]-s[i]));
    }
    cout<<min<<endl;
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main(){
	var S, T string
	fmt.Scan(&S, &T)
	ans := "No"
	for i := 0 ; i < len(T) ; i++ {
		tmp := S[len(S)-1:]
		S = tmp + S[:len(S)-1]
		// fmt.Println(S, tmp)

		if S == T {
			ans = "Yes"
			break
		}
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;

int main(){
  int N,W;
  cin >> N >> W;

  int v[1000],w[1000];
  for(int i=0;i<N;i++){
    cin >> v[i] >> w[i];
  }

  int DP[N+1][W+1];
  for(int i=0;i<=W;i++){
    DP[0][i]=0;
  }

  for(int i=1;i<=N;i++){
    for(int j=0;j<=W;j++){
      if(j<w[i-1])
        DP[i][j]=DP[i-1][j];
      else{
        if(DP[i-1][j]>DP[i][j-w[i-1]]+v[i-1])
          DP[i][j]=DP[i-1][j];
        else
          DP[i][j]=DP[i][j-w[i-1]]+v[i-1];
      }
    }
  }

  cout << DP[N][W] << endl;

  return 0;
}



Measured memory_bytes: 7024
#include <stdio.h>
#define N 100
#define WHITE 0
#define GRAY -1
#define BLACK 1
void dfs(void);
void visit(int);

int V[N+1][N+1];
int color[N+1];
int n;
int d[N+1],f[N+1];
int time;

int main(){
  int i,j,u,k,v;

  scanf("%d",&n);
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      V[i][j] = 0;
    }
  }
  for(i=1;i<=n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      V[u][v] = 1;
    }
  }
  dfs();
  for(i=1;i<=n;i++){
    printf("%d %d %d\n",i,d[i],f[i]);
  }
  return 0;
}

void dfs(void){
  int u;
  for(u=1;u<=n;u++){
    color[u] = WHITE;
  }
  time = 0;
  for(u=1;u<=n;u++){
    if(color[u] == WHITE)
      visit(u);
  }
}

void visit(int u){
  int i;
  color[u] = GRAY;
  d[u] = ++time;
  for(i=1;i<=n;i++){
    if(V[u][i] == 0) continue;
    if(color[i] == WHITE) 
      visit(i);
  }
  color[u] = BLACK;
  f[u] = ++time;
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int A, B, M;
  cin >> A >> B >> M;

  vector<int> a(A), b(B);

  for (int i = 0; i < A; ++i) cin >> a[i];
  for (int i = 0; i < B; ++i) cin >> b[i];
  
  int ans = *min_element(a.begin(), a.end()) + *min_element(b.begin(), b.end());

  for (int i = 0; i < M; ++i) {
    int x, y, z;
    cin >> x >> y >> z;

    ans = min(ans, a[x-1] + b[y-1] - z);
  }

  cout << ans << endl;

  return (0);
}


Measured memory_bytes: 3968
#include <cstdio>
#include <iostream>
using namespace std;

const long N=300000;

int main(){
	bool msp[N+1]; //月曜土曜素数
	
	for(long i=0; i<=5; ++i) msp[i]=false;
	for(long i=6; i<=N; ++i){
		if(i%7==1 || i%7==6)	 msp[i]=true;
		else msp[i]=false;
	}
	for(long i=6; i<=N; ++i){
		if(msp[i]){
			for(long j=1; i*(7*j-1)<=N; ++j){
				long a=7*j-1, b=7*j+1;
				msp[i*a]=false;
				if(i*b<=N) msp[i*b]=false;
			}
		}
	}
	
		
	while(1){
		long n;
		scanf(" %ld", &n);
		if(n==1) break;
		
		printf("%ld:", n);
		
		for(long i=1; 7*i-1<=n; ++i){
			long p=7*i-1;
			long q=7*i+1;
			if(q>N) q=1;
			
			if(n%p==0 && msp[p]) printf(" %ld", p);
			if(n%q==0 && msp[q]) printf(" %ld", q);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1484
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007


int main() {

  string S;
  cin >> S;

  long long ans = 0,b = 0;
  for(int i = 0;i < S.size();i++) {
    if(S.at(i) == 'W') ans += b;
    if(S.at(i) == 'B') b++;
  }

  cout << ans << endl;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

ll N;
vector<ll> G[10005];
ll c[100005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0;i < N-1;i++){
        ll a,b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i = 0;i < N;i++){
        cin >> c[i];
    }

    sort(c,c+N);
    reverse(c,c+N);

    ll sum = 0;

    for (int i = 1;i < N;i++){
        sum += c[i];
    }

    queue<P> que; // node,dist
    que.push(P(1,0));
    ll dist[10005];
    memset(dist,-1,sizeof(dist));
    dist[1] = 0;
    P las;

    while(que.size()){
        P p = que.front(); que.pop();
        ll now = p.first;
        ll d = p.second;
        las = p;
        for (int i = 0;i < G[now].size();i++){
            ll to = G[now][i];
            if(dist[to] == -1){
                dist[to] = d+1;
                que.push(P(to,dist[to]));
            }
        }
    }

    memset(dist,-1,sizeof(dist));
    que.push(P(las.first,0));
    dist[las.first] = 0;

    ll ans[10005];
    ans[las.first] = c[0];
    ll idx = 1;

    while(que.size()){
        P p = que.front(); que.pop();
        ll now = p.first;
        ll d = p.second;
        for (int i = 0;i < G[now].size();i++){
            ll to = G[now][i];
            if(dist[to] == -1){
                dist[to] = d+1;
                ans[to] = c[idx];
                idx++;
                que.push(P(to,dist[to]));
            }
        }
    }

    cout << sum << endl;

    for (int i = 1;i <= N;i++){
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;

}

Measured memory_bytes: 1408
//大文字->小文字 tolower(),逆はtoupper()
//int a = stoi(c); 文字列をintへ
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//円周率
const double PI = 3.14159265358979323846;

int main() {
	ll N, K; cin >> N >> K;
	ll R, S, P; cin >> R >> S >> P;
	string T; cin >> T;

	string U;
	rep(i, T.length()) {
		if (T[i] == 'r') U += 'p';
		if (T[i] == 's') U += 'r';
		if (T[i] == 'p') U += 's';
	}


	for (int i = K; i < U.length(); i++) {
		if (U[i] == U[i - K]) U[i] = 'a';
	}


	ll ans = 0;
	rep(i, U.size()) {
		if (U[i] == 'r') ans += R;
		if (U[i] == 's') ans += S;
		if (U[i] == 'p') ans += P;
	}

	cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll; typedef long double ld;
const int INF32 = 1e9+10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, H, W; cin >> N >> H >> W;
  cout << (N-H+1)*(N-W+1) << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 101


main(){

  int u,k,v,A[N][N],i,n,j;

  scanf("%d",&n);

  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      A[i][j]=0;
    }
  }

  for(i=1;i<=n;i++){
    scanf("%d %d",&u,&k);
    for(j=1;j<=k;j++){
      scanf("%d",&v);
      A[u][v]=1;
    }
  }

 for(i=1;i<=n;i++){ 
   for(j=1;j<=n-1;j++){
     printf("%d ",A[i][j]);
   }
   printf("%d",A[i][n]);
   printf("\n");
 }
 return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  string s, t;
  string result;
  
  cin >> n >> s >> t;
  
  for (int i = 0; i < n; i++) {
    result = result + s.at(i) + t.at(i);
  }
  
  cout << result << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N;
		long ans = 0;

		N = Integer.parseInt(sc.next());

		int[] a = new int[N];

		for(int i = 0; i < N; i++){
			a[i] = Integer.parseInt(sc.next());
		}

		long x = 0;
		long y = 0;

		x = a[0];
		for(int i = 1; i < N; i++){
			y += a[i];
		}
		ans = Math.abs(x-y);

		for(int i = 1; i < N-1; i++){
			x += a[i];
			y -= a[i];
			ans = Math.min(ans, Math.abs(x-y));
		}

		System.out.println(ans);

	}

}

Measured memory_bytes: 63480
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
using P = pair <int, int>;
 

int main() {
    vector<int>a(3);
    rep(i,3)cin >>a[i];
    sort(a.begin(),a.end());
    cout << a[1]-a[0] + a[2]-a[1] <<endl;
    
 }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

void dfs(int N, vector<vector<int>> &F, vector<int> &G, vector<int> &num, int s, int u){
  G[u] = s;
  for(int i=0;i<F[u].size();i++){
    int v = F[u][i];
    if(G[v]!=-1) continue;
    num[s]++;
    dfs(N,F,G,num,s,v);
  }
  return;
}

int main(){
  int N,M,K;
  cin >> N >> M >> K;
  vector<vector<int>> F(N+1,vector<int>(0));
  for(int i=0;i<M;i++){
    int a,b;
    cin >> a >> b;
    F[a].push_back(b);
    F[b].push_back(a);
  }
  for(int i=1;i<=N;i++){
    sort(F[i].begin(),F[i].end());
  }
  
  vector<int> G(N+1,-1), num(N+1,0);
  for(int s=1;s<=N;s++){
    if(G[s]==-1){
      dfs(N,F,G,num,s,s);
    }
    else{
      num[s] = num[G[s]];
    }
  }
  for(int i=1;i<=N;i++){
    num[i] -= F[i].size();
  }
  
  for(int i=0;i<K;i++){
    int c,d;
    cin >> c >> d;
    if(G[c]==G[d]){
      num[c]--;
      num[d]--;
    }
  }
  
  for(int i=1;i<=N;i++) cout << num[i] << " ";
  return 0;
}


Measured memory_bytes: 8704
# ABC141E - Who Says a Pun?
class RollingHash:
    def __init__(self, source: str, base=1007, mod=10 ** 9 + 7):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  # compute hash of interval [0, right)
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  # computer mod of power of base
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  # compute hash of interval [left, right)
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Measured memory_bytes: 20172
#include<iostream>
using namespace std;
int main(){
  int n;cin>>n;
  bool flag=false;
  for(int i=0;i<=n;++i){
    for(int j=0;j<=n;++j){
      if(i*4+j*7==n)flag=true;
    }
  }
  if(flag){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3604
s = list(map(int, input().split()))
n = int(input()) * 100
ss = [s[0] * 4, s[1] * 2, s[2], s[3] // 2]
ll = [25, 50, 100, 200]
cost = 0
while n > 0:
    if n >= 200:
        pass
    elif n >= 100:
        ss = ss[:3]
        ll = ll[:3]
    elif n >= 50:
        ss = ss[:2]
        ll = ll[:2]
    else:
        ss = ss[:1]
        ll = ll[:1]
    ssm = ss.index(min(ss))
    cnt = n // ll[ssm]
    cost += s[ssm] * cnt
    n -= ll[ssm] * cnt
print(cost)

Measured memory_bytes: 9224
#include <bits/stdc++.h>
using namespace std;

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 60;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

// h(n, r) = c(n+r-1, r)
struct combination
{
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1)
  {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
    fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i)
    ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k)
  {
    if (k < 0 || k > n)
    return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

ll modpow(ll a, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

int main()
{
  int x;
  cin >> x;
  int n = x/100;
  int d = x%100;
  if(d <= 5*n) cout << 1 << endl;
  else cout << 0 << endl;
}


Measured memory_bytes: 3584
#include <stdio.h>

int main ()
{
	int a=0;
	scanf("%d",&a);
	if(a%10==9||(a-(a%10))/10==9)
	{printf("Yes\n");
	}
	else {printf("No\n");
	}
	
	
	
	
	
	
	return 0;
}

Measured memory_bytes: 128
K = int(input())
A, B = map(int, input().split())

list=[]
for i in range(1000):
    list.append(i*K)

ans = []
for i in range(B-A+1):
    b = i+A
    ans.append(b)

    
for i in range(len(list)):
    if list[i] in ans:
        print("OK")
        exit()
    
print("NG")    

Measured memory_bytes: 62056
#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

int main() {
  ll n, k; cin >> n >> k;
  ll cnt = 0;
  ll ans = 0;
  for(ll i = 1; i <= n; i++) {
    if(i % k == 0) cnt++;
  }
  ans += (ll)(cnt * cnt * cnt);
  if(k % 2 == 0) {
    cnt = 0;
    for(ll i = 1; i <= n; i++) {
      if(i % k == (k/2)) cnt++;
    }
    ans += (ll)(cnt * cnt * cnt);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = []
B = []
S = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    S.append((i, a + b))
ans = 0
S.sort(key=lambda x: x[1], reverse=True)
for i in range(N):
    if i % 2 == 0:
        ans += A[S[i][0]]
    else:
        ans -= B[S[i][0]]

print(ans)

Measured memory_bytes: 26496
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <utility>


int main(){
  int N;
  scanf("%d", &N);
  std::vector<int > T(N), A(N);
  for (int i=0; i<N; i++){
    scanf("%d", &T[i]);
    scanf("%d", &A[i]);
  }
  std::pair<long long, long long > state;
  state=std::make_pair(1, 1);
  for (int i=0; i<N; i++){
    long long val1 = state.first;
    long long val2 = state.second;
    long long n=std::max((val1+T[i]-1)/T[i], (val2+A[i]-1)/A[i]);
    state=std::make_pair(n*T[i], n*A[i]);
    //printf("(%lld, %lld)\n", n*T[i], n*A[i]);
  }
  std::cout << state.first + state.second << std::endl;
  return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val aList = mutableListOf<Long>()
    val bList = mutableListOf<Long>()
    for (i in 1..n) {
        val (a, b) = readLine()!!.split(" ").map(String::toLong)
        aList.add(a)
        bList.add(b)
    }
    var count = 0L
    for (i in n - 1 downTo 0) {
        val temp = (aList[i] + count) % bList[i]
        val v = if (temp == 0L) 0 else (bList[i] - temp)
        count += v
    }
    println(count)
}


Measured memory_bytes: 62396
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
//#define uint __int128_t

 
#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define low(a,b) lower_bound(all(a),(b))-(a).begin()
#define upp(a,b) upper_bound(all(a),(b))-(a).begin()
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<vint> vvint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;

int N,M,cnt;
map<pint,int>mp;
struct edge{
    int to,cost;
    edge(int to,int cost):to(to),cost(cost){}
};
vector <edge> tree[500050];
ll dist[500050];
int f(int a,int b){
    if(mp.count(pint(a,b)))return mp[pint(a,b)];
    mp[pint(a,b)]=cnt;
    tree[a].pb(edge(cnt,1));
    tree[cnt].pb(edge(a,0));
    return cnt++;
}
void dijkstra(int s){
    priority_queue<pint,vpint,greater<pint>> que;
    fill(dist,dist+cnt,INF);
    dist[s]=0;
    que.push(pint(0,s));

    while(!que.empty()){
        pint p=que.top();
        que.pop();
        int v=p.se;
        if(dist[v]<p.fi)continue;
        rep(i,0,tree[v].size()){
            edge e=tree[v][i];
            if(dist[e.to]>dist[v]+e.cost){
                dist[e.to]=dist[v]+e.cost;
                que.push(pint(dist[e.to],e.to));
            }
        }
    }
}
signed main() {
    IOS();
    //(1ll<<N)シフト演算のオーバーフローに気をつける
    cin>>N>>M;
    cnt=N;
    rep(i,0,M){
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        a=f(a,c);
        b=f(b,c);
        tree[a].pb(edge(b,0));
        tree[b].pb(edge(a,0));
    }
    dijkstra(0);
    if(dist[N-1]!=INF)cout<<dist[N-1]<<endl;
    else cout<<-1<<endl;
    
    //rep(i,0,cnt)cout<<i+1<<" "<<dist[i]<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    return 0;
}

Measured memory_bytes: 75508
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int h, w, k, x1, y1, x2, y2;
    cin >> h >> w >> k >> x1 >> y1 >> x2 >> y2;
    char grid[h + 3][w + 3];
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> grid[i][j];
        }
    }
    int dist[h + 3][w + 3];
    pair<int, int>par[h + 3][w + 3];
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            dist[i][j] = -1;
            par[i][j] = make_pair(-1, -1);
        }
    }
    dist[x1][y1] = 0;
    par[x1][y1] = make_pair(0, 0);
    queue<pair<int, int> >q;
    q.push(make_pair(x1, y1));
    bool ok = false;
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        for(int i = y + 1; i <= min(w, y + k); i++){
            if(grid[x][i] == '@' || par[x][y] == par[x][i]){
                break;
            }
            if(dist[x][i] == -1 || dist[x][i] > dist[x][y] + 1){
                dist[x][i] = dist[x][y] + 1;
                par[x][i] = make_pair(x, y);
                q.push(make_pair(x, i));
            }
            if(x == x2 && i == y2){
                ok = true;
                break;
            }
        }
        if(ok){
            break;
        }
        for(int i = y - 1; i >= max(1, y - k); i--){
            if(grid[x][i] == '@' || par[x][y] == par[x][i]){
                break;
            }
            if(dist[x][i] == -1 || dist[x][i] > dist[x][y] + 1){
                dist[x][i] = dist[x][y] + 1;
                par[x][i] = make_pair(x, y);
                q.push(make_pair(x, i));
            }
            if(x == x2 && i == y2){
                ok = true;
                break;
            }
        }
        if(ok){
            break;
        }
        for(int i = x + 1; i <= min(h, x + k); i++){
            if(grid[i][y] == '@' || par[x][y] == par[i][y]){
                break;
            }
            if(dist[i][y] == -1 || dist[i][y] > dist[x][y] + 1){
                dist[i][y] = dist[x][y] + 1;
                par[i][y] = make_pair(x, y);
                q.push(make_pair(i, y));
            }
            if(i == x2 && y == y2){
                ok = true;
                break;
            }
        }
        if(ok){
            break;
        }
        for(int i = x - 1; i >= max(1, x - k); i--){
            if(grid[i][y] == '@' || par[x][y] == par[i][y]){
                break;
            }
            if(dist[i][y] == -1 || dist[i][y] > dist[x][y] + 1){
                dist[i][y] = dist[x][y] + 1;
                par[i][y] = make_pair(x, y);
                q.push(make_pair(i, y));
            }
            if(i == x2 && y == y2){
                ok = true;
                break;
            }
        }
        if(ok){
            break;
        }
    }
    cout << dist[x2][y2];
    return 0;
}

Measured memory_bytes: 39804
#include<bits/stdc++.h>
using namespace std;

int main(){
  int x1, y1, x2, y2, x3, y3, x4, y4;
  cin >> x1 >> y1 >> x2 >> y2;

  pair<int, int> vec = make_pair(x2-x1, y2-y1);

  x3 = x2 + (-1) * vec.second; y3 = y2 + vec.first;
  x4 = x3 + (-1) * vec.first; y4 = y3 + (-1) * vec.second;

  cout <<x3 << " " << y3 << " " << x4 << " " << y4 << endl;
  return 0;
    
}
  

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  if (n <= a) {
    cout << n << endl;
  } else {
    ll t = n / (a + b);
    ll r = n - (a + b) * t;
    ll ans = a * t + min(r, a);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define llu unsigned long long int
#define Endl endl
#define mod  998244353
#define mkp make_pair
#define pb push_back
#define cin(n) scanf("%d",&n)
#define cout(n) printf("%d ",n)
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d ",n)
#define bitget(n) __builtin_popcountll(n)
ll dx[] = {1,1,0,-1,-1,-1,0,1};
ll dy[] = {0,-1,-1,-1,0,1,1,1};
ll dxx[] = {1,-1,0,0};
ll dyy[] = {0,0,-1,1};
ll modexpo(ll x,ll y){if(y==0)return 1;if(y%2){ll viky=modexpo(x,y/2);
return (((x*viky)%mod)*viky)%mod;}else{ll viky=modexpo(x,y/2);return (viky*viky)%mod;
}}
bool isvalid(ll x,ll y,ll n, ll m) { return (x>=0&&x<n&&y>=0&&y<m); }
vector<ll>v[100011];

int main() {
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;

    cin>>n;

    ll ans = 0;

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

        ll x;
        cin>>x;
        if(i%2 == 0 and x%2){

            ans++;
        }
    }
    cout<<ans;

    return 0;
}

Measured memory_bytes: 5952
// https://atcoder.jp/contests/dp/tasks/dp_b
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  int arr[N], ans[N];
  fill_n(ans, N, 1000000000);
  ans[0] = 0;

  for (int i = 0; i < N; ++i)
    cin >> arr[i];

  auto cost = [&](int i, int j) { return abs(arr[i] - arr[j]); };
  for (int j = 1; j < N; ++j)
    for (int k = 1; k <= K; ++k)
      if (k <= j)
        ans[j] = min(ans[j], cost(j - k, j) + ans[j - k]);

  cout << ans[N - 1] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>

using namespace std;

typedef string::const_iterator State;
class ParseError {};

typedef unsigned long long ull;
#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define all(a) (a).begin(), (a).end()

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

int expression(State &begin);
int term(State &begin);
int number(State &begin);
int factor(State &begin);

int number(State &begin) {
	int ret = 0;

	while (isdigit(*begin)) {
		ret *= 10;
		ret += *begin - '0';
		begin++;
	}
	return ret;
}

int term(State &begin) {
	int ret = factor(begin);

	for (;;) {
		if (*begin == '*') {
			begin++;
			ret *= factor(begin);
		} else if (*begin == '/') {
			begin++;
			ret /= factor(begin);
		} else {
			break;
		}
	}
	return ret;
}

int expression(State &begin) {
	int ret = term(begin);

	for (;;) {
		if (*begin == '+') {
			begin++;
			ret += term(begin);
		} else if (*begin == '-') {
			begin++;
			ret -= term(begin);
		} else {
			break;
		}
	}

	return ret;
}

int factor(State &begin) {
	if (*begin == '(') {
		begin++; // '('テ」ツつ津ゥツ」ツ崚」ツ?ーテ」ツ?凖」ツ??
		int ret = expression(begin);
		begin++; // ')'テ」ツつ津ゥツ」ツ崚」ツ?ーテ」ツ?凖」ツ??
		return ret;
	} else {
		return number(begin);
	}
}

int main(void) {
	int N;
	cin >> N;
	cin.ignore();
	for (int i = 0; i < N; i++) {
		string s;
		getline(cin, s);
		State begin = s.begin();
		cout << expression(begin) << endl;
	}
	return 0;
}

Measured memory_bytes: 1212
inputs = [int(x) for x in input().split()]
a = inputs[0]
b = inputs[1]
c = inputs[2]
d = inputs[3]

# Avoid using 0
if a == 0 and a + 1 <= b:
    a += 1
if b == 0 and b - 1 >= a:
    b -= 1
if c == 0 and c + 1 <= d:
    c += 1
if d == 0 and d - 1 >= c:
    d -= 1

if (a > 0 and b > 0 and c < 0 and d < 0) or (a < 0 and b < 0 and c > 0 and d > 0):
    # Return the max negative value
    print(-(min(abs(a), abs(b)) * min(abs(c), abs(d))))    
else:
    # Return the max positive value
    print(max(a * c, b * d))

Measured memory_bytes: 61960