akhauriyash/Code-Regression huggingface dataset:
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
ll max_v = 0;
map<pair<ll,ll>,ll> edge_map;
vector<pair<ll,ll>> ememo;
vector<vector<ll>> edges(100010,vector<ll>());

void saiki(ll now,ll parent, ll used){
    for (auto e : edges[now]) {
        if(e == parent)continue;
        used++;
        edge_map[{now,e}] = used%max_v;
        edge_map[{e,now}] = used%max_v;
        saiki(e, now, used%max_v);
    }
}

int main() {
    ll n;
    std::cin >> n;
    
    for (int i = 0; i < n-1; i++) {
        ll t1,t2;
        std::cin >> t1>>t2;
        t1--;
        t2--;
        edge_map[{t1,t2}] = -1;
        edge_map[{t2,t1}] = -1;

        ememo.push_back({t1,t2});

        edges[t1].push_back(t2);
        edges[t2].push_back(t1);
    }

    
    ll max_i = -1;
    for (int i = 0; i < n; i++) {
        if(edges[i].size()>max_v){
            max_v = edges[i].size();
            max_i = i;
        }
    }
    
    saiki(max_i,-1, -1);
    
    std::cout << max_v << std::endl;

    for (int i = 0; i < n-1; i++) {
        std::cout << edge_map[ ememo[i] ] +1 << std::endl;
    }
}


Measured memory_bytes: 20980
use std::vec::Vec;
use std::cmp::*;
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let s: Vec<char> = read::<String>().chars().collect();
    let n = s.len();
    let mut left = Vec::new();
    let mut right = Vec::new();
    let mut mid = Vec::new();
    if n % 2 == 1 {
      mid.push(s[n/2]);
    }

    for i in 0..n/2 {
      left.push(s[i]);
    }

    for i in (n+1)/2..n {
      right.push(s[i]);
    }

    let mut ans = right.len();
    let mut c = '0';
    if n % 2 == 1 {
      c = mid[0];
      ans += 1;
    } else {
      c = right[0];
    }

    left.reverse();
    for i in 0..right.len() {
      if c == right[i] && c == left[i] {
        ans += 1;
      } else {
        break
      }
    }

    println!("{}", ans);
    //println!("{:?}", s);
    //println!("{:?} {:?} {:?}", left, mid, right);
}


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

using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back

typedef unsigned int uint;
typedef long long ll;
typedef pair<int,int> pii;

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

int l[200];

int main(){
	int n=read();
	REP(i,2*n)
		l[i]=read();
	int ans=0;
	sort(l,l+2*n);
	REP(i,n)
		ans+=l[i*2];
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define MAXN 200010
using namespace std;

int n,m;

struct node{
	int pos;
	int index;
}X[100010];

bool cmp(node a,node b){
	return a.pos<b.pos;
} 

int main(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		X[i].pos=x;
		X[i].index=i;
	}
	sort(X+1,X+1+n,cmp);
	for(int i=1;i<=n;i++){
		printf("%d ",X[i].index);
	}
//	printf("\n");
} 

Measured memory_bytes: 4600
s = input()
t = input()
s_list = list(s)

for i in range(len(s)-len(t)+1):
    flg = True
    for j in range(len(t)):
        if not (s[-len(t)-i+j] == "?" or s[-len(t)-i+j] == t[j]):
            flg = False
            break
    
    if flg:
        for j in range(len(t)):
            s_list[-len(t)-i+j] = t[j]
        
        s = "".join(s_list)
        s = s.replace("?", "a")

if s.count("?") > 0:
    print("UNRESTORABLE")
else:
    print(s)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int Q;
vector<pii> lr;
void input() {
  int x, y, z;
  cin >> Q;
  lr.resize(Q);
  rep(i, 0, Q - 1) { cin >> lr[i].first >> lr[i].second; };
}

bool is_prime[MX + 2] = {};
vector<int> P;
void Eratosthenes(const int N) {
  for (int i = 0; i <= N; i++) {
    is_prime[i] = true;  // initialize.
  }
  for (int i = 2; i <= N; i++) {
    if (is_prime[i]) {
      for (int j = 2 * i; j <= N; j += i) {
        is_prime[j] = false;
      }
      P.emplace_back(i);
    }
  }
}

int sumc[MX + 3] = {};
void solve() {
  Eratosthenes(MX);
  sumc[0] = 0;
  rep(i, 3, MX) {
    sumc[i] = sumc[i - 1] + ((is_prime[i] && is_prime[(i + 1) / 2]) ? 1 : 0);
  }
  // rep(i, 0, 24) {
  //   cout << i;
  //   debug(sumc[i]);
  // }
  for (auto x : lr) {
    cout << sumc[x.second] - sumc[x.first - 1] << endl;
  }

  ;
  ;
}
signed main() {
  input();
  solve();
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector <int> H(N);

    for(int i = 0; i < N; i++)
        cin >> H[i];
    int count = 0;
    int max_hight = 0;
    for(int i = 0; i < N; i++)
    {
        if(max_hight <= H[i])
        {
            count++;
            max_hight = H[i];
        }
    }

    cout << count << endl;
    return 0;  

}

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

int main() {
    int n;
    std::string s;
    std::cin >> n >> s;

    i64 cnt[3] {};
    for (auto c : s) cnt[c == 'R' ? 0 : c == 'G' ? 1 : 2]++;

    i64 ret = cnt[0] * cnt[1] * cnt[2];
    for (int i = 0; i < n; i++) for (int j = 1; i - j >= 0 && i + j < n; j++) {
        if (s[i] != s[i - j] && s[i] != s[i + j] && s[i - j] != s[i + j]) ret--;
    }

    std::cout << ret << std::endl;

    return 0;
}


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

using namespace std;

int main() {

	int n;
	cin >> n ;

	int counter = 0;

	vector<int> p(n, 0);
	vector<int> pp(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}

	pp = p;
	sort(pp.begin(), pp.end());

	for (int i = 0; i < n; i++) {
		if (p[i] != pp[i]) { counter++; }
	}
	if (counter > 2) { cout << "NO" << endl; }
	else { cout << "YES" << endl; }

}

Measured memory_bytes: 256
#include <stdio.h>

int zeller(int y, int m, int d){
	if(m <= 2){
		y--;
		m += 12;
	}

	int J = (int)(y/100);
	int K = y - (int)(y/100)*100;

	return (d + (int)((m+1)*26/10) + K + (int)(K/4) + (int)(J/4) + 5 * J + 5) % 7;
}

int main(void){
	int y, m, d;
	y = 2004;
	char *wday[7] = {
		"Monday",
		"Tuesday",
		"Wednesday",
		"Thursday",
		"Friday",
		"Saturday",
		"Sunday",
	};
	while(true){
		scanf("%d %d", &m, &d);
		if(m == 0){ break; }
		int w = zeller(y, m , d);
		puts(wday[w]);
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<float.h>
#include<cfloat>
#include<string>
#include<ctype.h>
#include<algorithm>
#include<errno.h>
#include<cerrno>
#include<assert.h>
#include<cassert> 
#include<map>
#include<memory.h>
#include<cctype>
#include<ctype.h>
#include<math.h>
#include<vector> 
#include<cstdio> 
#include<set>
#include<string.h>
#include<stdio.h>
#include<new>
#include<memory>
#include<cmath>
#include<queue>
#include<cstring>
#define ll long long
#define fo(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define br break
#define ct continue
#define pb push_back
#define pi 3.141592653589793238462643383279502884197169
#define F first
#define S second
#define pii pair<int,int>  
#define em empty()
#define vei vector<int>
#define ves vector<string>
#define qui queue<int> 
#define qu queue
using namespace std;
int main()
{int a,b,c;
 cin>>a>>b>>c;
 if(a!=b && b!=c && a!=c)
 {cout<<"3"<<endl;
 }
 else if(a==b && b!=c && a!=c || a!=b && b==c && a!=c || a!=b && b!=c && a==c)
 {cout<<"2"<<endl;
 }
 else if(a==b && b==c)
 {cout<<"1"<<endl;
 } 
 system("pause");
 return 0;
}

Measured memory_bytes: 884
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <queue>
#include <string>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int> ;
using vl = vector<ll>;

int main(){
    string s;
    cin >> s;
    if(s[s.length()-1] != 's'){
        cout << s << "s" << endl;
    }else{
        cout << s << "es" << endl; 
    }


    return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef long long ll;

int main(){

  char s[5];

  scanf("%s", s);

  if(s[1] == 'R') printf("ABC\n");

  else printf("ARC\n");  
  return 0;
}


Measured memory_bytes: 1612
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main() {
    int n = 0;
    cin >> n;
    map<string,int> counter;
    string tmp = "";
 
    for(int i = 0; i < n;i++){
        cin >> tmp;
        counter[tmp] ++;
    }
    int maxStr = 0;
    
    for(auto i: counter) maxStr = max(maxStr,i.second);
    for(auto i: counter){
        if(i.second == maxStr){
            cout << i.first << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 25216
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use num_traits::*;
use superslice::*;
use std::ops::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;


#[fastout]
fn solve() {
    const MOD: usize = 1_000_000_007;
    const INF: usize = std::usize::MAX;
    
    input!{
        a: usize, mut b: usize, mut c: usize,
        k: usize,
    }
    
    let mut cnt = 0;

    while a >= b {
        cnt += 1;
        b *= 2;
    }

    while b >= c {
        cnt += 1;
        c *= 2;
    }


    if cnt <= k {
        println!("Yes");
    } else {
        println!("No");
    }
    
}

fn main() {
    solve()
}

#[cfg(test)]
mod test {
    use super::solve;
}


Measured memory_bytes: 2168
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
class c{
    public static void Main(){
        long k = long.Parse(Console.ReadLine());
        long num = 0;
        long ans = 1;
        bool[] already = new bool[k];
        if(k%2 == 0){
            ans = -1;
        }
        else{
            while(true){
                num = (num*10 + 7)%k;
                if(num == 0){
                    break;
                }
                if(already[num]){
                    ans = -1;
                    break;
                }
                already[num] = true;
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 17844
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // long long64_t, long long*_t
#include <cstdio> // prlong longf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
using namespace std;
int main(){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    if(a+b<2*c){
        cout << a*x+b*y << endl;
    }
    else{
      if(x==y){
        cout << c*2*x << endl;
      }
      else if(x>y){
        int a1,b1;
        a1=y*2*c+(x-y)*a;
        b1=y*2*c+(x-y)*2*c;
        cout << min(a1,b1) << endl;
      }
      else{
        int a1,b1;
        a1=x*2*c+(y-x)*b;
        b1=x*2*c+(y-x)*2*c;
        cout << min(a1,b1) << endl;
      }
    }
}


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code
int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	cout << 48 - n << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
int main() {
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> a(h);
  for (int i = 0; i < h; ++i)
    cin >> a[i];
  int ans = 0;
  for (int i = 0; i < (1 << h); ++i) {
    for (int j = 0; j < (1 << w); ++j) {
      vector<string> b(a);
      int cnt = 0;
      for (int p = 0; p < h; ++p)
        for (int q = 0; q < w; ++q) {
          if ((i & (1 << p)) || (j & (1 << q)))
            b[p][q] = '.';
          cnt += b[p][q] == '#';
        }
      ans += cnt == k;
    }
  }
  cout << ans;
}

Measured memory_bytes: 3632
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+10;

string s;
int d[maxn]={0};

int main(){
  cin>>s;s="L"+s+"R";int n=s.length();
  int prev=1;int mid=0;
  for(int i=2;i<n;i++){
    if (s[i-1]=='R' && s[i]=='L') mid=i;
    if (s[i-1]=='L' && s[i]=='R'){
      int nr=mid-prev;int nl=i-mid;int sl=i-prev;
      if (nr>nl){
        d[mid-1]=(sl+1)/2;
        d[mid]=sl-d[mid-1];
      }
      else{
        d[mid]=(sl+1)/2;
        d[mid-1]=sl-d[mid];
      }
      int time=max(nr-1,nl-1);
      if (time%2==1){
        int tmp=d[mid-1];d[mid-1]=d[mid];d[mid]=tmp;
      }
      prev=i;
    }
  }
  for(int i=1;i<=n-2;i++) cout<<d[i]<<" ";cout<<endl;
}


Measured memory_bytes: 1020
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define sz(x) ll(x.size())
using namespace std;

int main() {
  ll a,b,ans=0;
  cin >> a >> b;
  if(a<=5) ans=0;
  else if(a>=13) ans=b;
  else ans=b/2;
  cout << ans << endl;
}


Measured memory_bytes: 256
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
cuma = [0]
cumb  = [0]
for a in A:
    cuma.append(cuma[-1] + a)
for b in B:
    cumb.append(cumb[-1] + b)
from bisect import bisect_left
ans = 0
for i in range(n+1):
    if k < cuma[i]: break
    idx = bisect_left(cumb, k - cuma[i] + 1)
    ans = max(ans, i + idx - 1)
print(ans)

Measured memory_bytes: 47224
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define x first
#define y second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

const LL MAX = 1e18 + 10;
const int N = 100 + 5;

int n;
LL f[N];
vector<PII> P[N];

void init(){
	f[0] = f[1] = 1;
	n = 1;
	while(f[n] < MAX) ++n, f[n] = f[n - 1] + f[n - 2];
	f[n + 1] = f[n] + f[n - 1];
	--n;
	P[0].pb(mp(0, 1));
	P[1].pb(mp(1, 2)), P[1].pb(mp(1, 3));

	For(i, 1, n - 1){
		for(PII s : P[i]){
			LL u = s.x, v = s.y;
			//printf("(%lld, %lld) ", u, v);
			if(u == v) continue;
			if(u > v) swap(u, v);
			u += v;
			while(u <= f[i + 3]) P[i + 1].pb(mp(u, v)), u += v;
		}
		//puts("");
	}

	For(i, 1, n){
		sort(P[i].begin(), P[i].end());
		P[i].resize(unique(P[i].begin(), P[i].end()) - P[i].begin());
	}
}

const int Mod = 1e9 + 7;

int main(){
	init();
	int q;
	scanf("%d", &q);
	while(q--){
		LL x, y;
		scanf("%lld%lld", &x, &y);
		if(x > y) swap(x, y);

		int ans = 0;
		while(f[ans + 1] <= x && f[ans + 2] <= y) ++ans;

		if(ans <= 1){
			printf("1 %lld\n", x % Mod * (y % Mod) % Mod);
			continue;
		}
		LL cnt = 0;

		for(PII p : P[ans]){
			LL u = p.x, v = p.y;
			if(u < v) swap(u, v);
			if(u / v >= 2) continue;
			//printf("%lld %lld\n", u, v);
			if(v <= y && x >= u) (cnt += (x - u + v) / v) %= Mod;
			if(v <= x && y >= u) (cnt += (y - u + v) / v) %= Mod;
		}

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

Measured memory_bytes: 4096
n = int(input())

t_list = [0]
x_list = [0]
y_list = [0]

for a in range(n):
    t, x, y = map(int, input().split())
    t_list.append(t)
    x_list.append(x)
    y_list.append(y)

for a in range(1, n+1):
    dt = t_list[a] - t_list[a-1]
    dx = x_list[a] - x_list[a-1]
    dy = y_list[a] - y_list[a-1]

    if abs(dx) + abs(dy) <= dt:
        if (dx + dy) % 2 == dt % 2:
            ans = True
        else:
            ans = False
            break
    else:
        ans = False
        break

if ans:
    print('Yes')
else:
    print('No')


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

#define ll long long
#define deb(x) cerr << #x << ":" << x << "\n"
#define all(x) x.begin(),x.end()

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

void solve()
{
    int x;
    cin>>x;
    cout<<1-x<<"\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3648
i = 0
a = Array.new
a[0] = gets.to_i
while a[i] != 0 do
	i += 1
	a[i] = gets.to_i
end
i = 0
while a[i] != 0 do
	puts "Case #{i+1}: #{a[i]}"
	i += 1
end

Measured memory_bytes: 8828
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x;
int main()
{
    ll ans=0;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&x),ans^=x;
    if(!ans) printf("Yes\n");
    else printf("No\n");
    return 0;
}

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

int32_t main()
{
  string s;
  cin>>s;
  int prev=0,temp=1;
  vector<int> mods(2019,0);
  for(int i=s.length()-1; i>=0; i--)
  {
  int sum=(prev+(s[i]-'0')*temp)%2019;
  mods[sum]++;
  temp=(temp*10)%2019;
  prev=sum;
  }
  int ans=0;
  mods[0]++;
  for(int i=0; i<2019; i++)
  {
    if(mods[i])
    {
    ans+=(mods[i]*(mods[i]-1))/2; 
    }
  }
cout<<ans;
  return 0;
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
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 m =1000000000;
  for(int i=0;i<N-K+1;i++) m = min(m,H[K+i-1]-H[i]);
  printf("%d\n",m);
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <numeric>
#include <utility>
#include <ctime>
#define INF 100000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;
/*---------------------------------------------------*/

int main(){
  int n,m,p,x;
  int t[105];
  cin>>n;
  rep(i,n)cin>>t[i];
  cin>>m;
  rep(i,m){
    cin>>p>>x;
    int sum=0;
    rep(i,n){
      if(p-1==i)sum+=x;
      else sum+=t[i];
    }
    cout<<sum<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
@form = gets.strip

def solve(is, i)
  if i >= @form.size - 1
    res = 0

    last_index = 0
    is.each do |index|
      res += @form[last_index...(index + 1)].to_i
      last_index = index + 1
    end

    res += @form[last_index...@form.size].to_i

    res
  else
    indexes = is.dup

    res = 0
    res += solve(indexes, i + 1)
    indexes << i
    res += solve(indexes, i + 1)

    res
  end
end

puts solve([], 0)


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int t,i,sum=0,p=2;
    cin >> t;
    t = 3*t;
    long long int a[t];
    for(i=0;i<t;i++)
    {
        cin >>a[i];

    }
    sort(a,a+t);
    for(i=0;i<t;i=i+3)
    {sum= sum+a[t-p];
    p=p+2;}
    cout<<sum;
    return 0;

}


Measured memory_bytes: 5880
#include<iostream>
#include<fstream>
#include<math.h>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
#include<set>

using namespace std;

#define forn(i,n) for(int i=0;i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
#define esta(x,v) (find((v).begin(),(v).end(),(x)) !=  (v).end())
#define index(x,v) (find((v).begin(),(v).end(),(x)) - (v).begin())
#define debug(x) cout << #x << " = "  << x << endl
#define pb push_back
#define mp make_pair

typedef long long tint;
typedef pair<int,int> pint;
typedef pair<tint,tint> ptint;
typedef unsigned long long utint;
typedef long double ldouble;

typedef vector<int> vint;

int toNumber (string s)
{
	int Number;
	if ( ! (istringstream(s) >> Number) ) Number = 0; // el string vacio lo manda al cero
	return Number;
}

string toString (int number)
{
    ostringstream ostr;
    ostr << number;
    return  ostr.str();
}

tint ele(tint a, tint b){
	if(b==0)return 1;
	if(b%2==0){
		return ele(a*a, b/2);
	}else{
		return a*ele(a*a, b/2);
	}
}

tint mcd(tint a, tint b){
	if(a==0)return b;
	return mcd(b%a, a);
}

double d_abs(long a, long b){
	if(a>b){
		return a-b;
	}
	return b-a;
}

void solve(){
	int a, b, n;
	string s;
	vector<tint> v;
	cin>>s;
	n=(int)(s.size());
	int pasos=n;
	string ini=s;
	for(char a='a'; a<='z'; a++){
		int pa=0;
		s=ini;
		while(true){
			char cs=s[0];
			bool uniq=true;
			forn(i, s.size()){
				if(s[i]!=cs)uniq=false;
			}
			if(uniq)break;
			string ot="";
			forn(i, s.size()-1){
				if(s[i]!=a){
					ot+=s[i+1];
				}else{
					ot+=s[i];
				}
			}
			pa++;
			s=ot;
		}
		pasos=min(pasos, pa);
	}
	cout<<pasos<<endl;
}




int main (){
	int T;
	T=1;
	while(T--){
		solve();
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,ac=0,tle=0,wa=0,re=0;
	string s;
	cin>>n;
	while(n--)
	{
		cin>>s;
		if(s=="AC")ac++;
		if(s=="WA")wa++;
		if(s=="TLE")tle++;
		if(s=="RE")re++;
		
	}
	cout<<"AC x "<<ac<<endl;
	cout<<"WA x "<<wa<<endl;
	cout<<"TLE x "<<tle<<endl;
	cout<<"RE x "<<re<<endl;
    return 0;
}

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

int main() {
  int n; cin >> n;
  vector<int> b(n-1);
  rep(i,n-1) cin >> b[i];

  vector<int> a(n, 0);
  int ans = 0;
  rep(i,n-1) {
    if (i == 0) {
      a[i] = b[i];
      a[i+1] = b[i];
    } else {
      a[i+1] = b[i];
      if (a[i] > a[i+1]) a[i] = b[i];
    }
  }
  rep(i,n) ans += a[i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
namespace my_header {
#define pb push_back
#define mp make_pair
#define pir pair<int, int>
#define vec vector<int>
#define pc putchar
#define clr(t) memset(t, 0, sizeof t)
#define pse(t, v) memset(t, v, sizeof t)
#define bl puts("")
#define wn(x) wr(x), bl
#define ws(x) wr(x), pc(' ')
    const int INF = 0x3f3f3f3f;
    typedef long long LL;
    typedef double DB;
    inline char gchar() {
        char ret = getchar();
        for(; (ret == '\n' || ret == '\r' || ret == ' ') && ret != EOF; ret = getchar());
        return ret; }
    template<class T> inline void fr(T &ret, char c = ' ', int flg = 1) {
        for(c = getchar(); (c < '0' || '9' < c) && c != '-'; c = getchar());
        if (c == '-') { flg = -1; c = getchar(); }
        for(ret = 0; '0' <= c && c <= '9'; c = getchar())
            ret = ret * 10 + c - '0';
        ret = ret * flg; }
    inline int fr() { int t; fr(t); return t; }
    template<class T> inline void fr(T&a, T&b) { fr(a), fr(b); }
    template<class T> inline void fr(T&a, T&b, T&c) { fr(a), fr(b), fr(c); }
    template<class T> inline char wr(T a, int b = 10, bool p = 1) {
        return a < 0 ? pc('-'), wr(-a, b, 0) : (a == 0 ? (p ? pc('0') : p) : 
            (wr(a/b, b, 0), pc('0' + a % b)));
    }
    template<class T> inline void wt(T a) { wn(a); }
    template<class T> inline void wt(T a, T b) { ws(a), wn(b); }
    template<class T> inline void wt(T a, T b, T c) { ws(a), ws(b), wn(c); }
    template<class T> inline void wt(T a, T b, T c, T d) { ws(a), ws(b), ws(c), wn(d); }
    template<class T> inline T gcd(T a, T b) {
        return b == 0 ? a : gcd(b, a % b); }
    template<class T> inline T fpw(T b, T i, T _m, T r = 1) {
        for(; i; i >>= 1, b = b * b % _m)
            if(i & 1) r = r * b % _m;
        return r; }
};
using namespace my_header;

LL n, a, b, c, d;

int main() {
#ifdef lol
	freopen("b.in", "r", stdin);
	freopen("b.out", "w", stdout);
#endif

	fr(n, a, b);
	fr(c, d);
	bool ok = false;

	for (int i = 0; i < n; ++i) {
		if (c * i - d * (n - i - 1) <= b - a &&
			b - a <= d * i - c * (n - i - 1))
			ok = true;
	}

	if (ok) {
		puts("YES");
	} else puts("NO");

	return 0;
}


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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
typedef struct aaaaa{
  int x,y,t;
}Grid;
using namespace std;
int main(){
  int n;
  cin>>n;
  int num[111]={};
  vector<int>prime;
  prime.pb(2);
  for(int i=3;i<200;i++){
    bool flag=true;
    for(int j=2;j<=sqrt(i);j++)
      if(i%j==0)flag=false;
    if(flag)prime.pb(i);
  }
  for(int i=1;i<=n;i++){
    ll numm=i;
    for(int j=0;j<prime.size();j++){
      while(numm%prime[j]==0){
	num[prime[j]]++;
	numm/=prime[j];
      }
    }
  }
  ll ans=0;
  vector<int>hoge;
  for(int i=0;i<111;i++){
    if(num[i]>1){hoge.pb(num[i]);}
  }
  for(int i=0;i<(1<<hoge.size());i++){
    vector<ll>cnt;
    for(int j=0;j<hoge.size();j++){
      if(i&(1<<j))cnt.pb(hoge[j]);
    }
    if(cnt.size()>3)continue;
    if(cnt.size()==3){
      if(cnt[0]>=2&&cnt[1]>=4&&cnt[2]>=4)ans++;
      if(cnt[0]>=4&&cnt[1]>=2&&cnt[2]>=4)ans++;
      if(cnt[0]>=4&&cnt[1]>=4&&cnt[2]>=2)ans++;
    }else if(cnt.size()==2){
      if(cnt[0]>=14&&cnt[1]>=4)ans++;
      if(cnt[0]>=4&&cnt[1]>=14)ans++;

      if(cnt[0]>=24&&cnt[1]>=2)ans++;
      if(cnt[0]>=2&&cnt[1]>=24)ans++;
    }else if(cnt.size()==1){
      if(cnt[0]>=74)ans++;
    }
  }
   cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] l = new int[n];
        int max = 0;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            l[i] = sc.nextInt();
            if (max < l[i]) {
                max = l[i];
            }
            sum = sum + l[i];
        }
        int nsum = sum - max;
        if (max < nsum) {
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }

    }
}





Measured memory_bytes: 22996
//
// B - ∵∴∵
//

#include <iostream>

using namespace std;

int main() {

    string O, E;
    cin >> O;
    cin >> E;

    for (int i = 0; i < O.length() + E.length(); i++) {
        if (i % 2) {
            cout << E[i / 2];
        } else {
            cout << O[i / 2];
        }
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    string ans;
    cin>>ans;
    REP(i,3){
        if(ans[i]=='9')ans[i]='1';
        else ans[i]='9';
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;typedef vector<ll> vll;
#define fill(a,b) memset(a, b, sizeof (a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int maxn = 2000100;

int main(){
        _ios;
        int k; cin >> k;
        int a,b; cin >> a >> b;
        int dis = abs(a-b);
        for(int i=a;i<=b;i++)
            {
                if(i%k==0)
                {
                        cout<<"OK";
                        return 0;
                }

            }
            cout<<"NG";

return 0;
}



Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
 
const int mod = 1000000007;
int dp[100005][2];
 
int main() {
  string s;
  cin >> s;
  int n = s.size();
  dp[0][0] = 1;
  rep(i,n) {
    { // a+b = 0
      if (s[i] == '0') {
        dp[i+1][0] = dp[i][0];
        dp[i+1][1] = dp[i][1];
      } else {
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod;
      }
    }
    { // a+b = 1
      if (s[i] == '0') {
        (dp[i+1][1] += dp[i][1]*2 % mod) %= mod;
      } else {
        (dp[i+1][0] += dp[i][0]*2 % mod) %= mod;
        (dp[i+1][1] += dp[i][1]*2 % mod) %= mod;
      }
    }
  }
  int ans = (dp[n][0]+dp[n][1]) % mod;
  cout << ans << endl;
  return 0;
}    

Measured memory_bytes: 1280
// Pile of k stones
// If any of k - a[i] = Second wins! Then First win!
// If all of k - a[i] = First Wins, then Second wins!
// if(no move!) then second
// pile[0] = Second
#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define SECOND (false)
#define FIRST (true)
int main() {
	int n,K;
	cin>>n>>K;
	vector<int> a (n);
	for(int i=0;i<n;i++) {
		cin>>a[i];
	}
	vector<bool> dp (K+1);
	for(int k = 0; k<= K; k++) {
		dp[k] = SECOND;
		for(int i=0;i<n;i++) {
			if( k - a[i] >= 0 ) {
				if(dp[k-a[i]] == SECOND) {
					dp[k] = FIRST;
					break;
				}
			} else {
				break;
			}
		}
	}
	cout<< (dp[K] == FIRST ? "First" : "Second")<<endl;
	return 0;
}


Measured memory_bytes: 256
N, M = map(int,input().split())

if N%2==0:
  for i in range(1,M+1):
    if i > N/4:
      print(f'{i+1} {N+1-i}')
    else:
      print(f'{i} {N+1-i}')
else:
  for i in range(1,M+1):
    print(f'{i} {N+1-i}')

Measured memory_bytes: 9128
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const ll mod = 1e9+7;

int main() {
		int N, M;
		cin >> N >> M;
		vector<bool> a(N+1, true);
		for (int i = 0; i < M; i++) {
				int t;
				cin >> t;
				a[t] = false;
		}

		vector<ll> dp(N+1, 0);
		dp[0] = 1;
		for (int pos = 0; pos < N; ++pos) {
				for (int next = pos+1; next <= min(N, pos+2); ++next) {
						if (a[next]) {
								dp[next] += dp[pos];
								dp[next] %= mod;
						}
				}
		}

		cout << dp[N] << endl;

		return 0;
}


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

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MAX 1000000001;
using namespace std;
typedef long long ll;

int n;

int main(){
  std::cin >> n;
  rep(i,1,10){
    int tmp = i*111;
    if(n <= tmp){
      std::cout << tmp << '\n';
      return 0;
    }
  }
}


Measured memory_bytes: 256
<?php
 
$sc = new Scanner();
 
$n = $sc->next();
 
$p = [];
for ($i = 0; $i < $n; $i++) {
    $p[] = $sc->nextInt();
}
rsort($p);
$p[0] = $p[0] / 2;
 
echo array_sum($p) . PHP_EOL;
 
class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}

Measured memory_bytes: 4984
n = int(input())
res = n
for i in range(n + 1):
  t = i
  c = 0
  while t > 0:
    c += t % 9
    t //= 9
  t = n - i
  while t > 0:
    c += t % 6
    t //= 6
  if res > c:
    res = c
print(res)

Measured memory_bytes: 3060
K = int(input())

flag=0
lis=[]
for i in range(0, 10):
  if i == 0:
    starti = 0
    endi = 10
  else:
    starti = max(i-1, 0)
    endi = min(i+2, 10)
  for j in range(starti, endi):
    if i == 0 and j == 0:
      startj = 0
      endj = 10
    else:
      startj = max(j-1, 0)
      endj = min(j+2, 10)
    for k in range(startj, endj):
      if i == 0 and j == 0 and k == 0:
        startk = 0
        endk = 10
      else:
        startk = max(k-1, 0)
        endk = min(k+2, 10)
      for l in range(startk, endk):
        if i == 0 and j == 0 and k==0 and l == 0:
          startl = 0
          endl = 10
        else:
          startl = max(l-1, 0)
          endl = min(l+2, 10)
        for m in range(startl, endl):
          if i == 0 and j == 0 and k==0 and l == 0 and m==0:
            startm = 0
            endm = 10
          else:
            startm = max(m-1, 0)
            endm = min(m+2, 10)
          for n in range(startm, endm):
            if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0:
              startn = 0
              endn = 10
            else:
              startn = max(n-1, 0)
              endn = min(n+2, 10)
            for o in range(startn, endn):
              if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0:
                starto = 0
                endo = 10
              else:
                starto = max(o-1, 0)
                endo = min(o+2, 10)
              for p in range(starto, endo):
                if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0:
                  startp = 0
                  endp = 10
                else:
                  startp = max(p-1, 0)
                  endp = min(p+2, 10)
                for q in range(startp, endp):
                  if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0 and q==0:
                    startq = 0
                    endq = 10
                  else:
                    startq = max(q-1, 0)
                    endq = min(q+2, 10)
                  for r in range(startq, endq):
                    if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0 and q==0 and r==0:
                      startr = 0
                      endr = 10
                    else:
                      startr = max(r-1, 0)
                      endr = min(r+2, 10)
                    lis.append(r+10*q+100*p+1000*o+10000*n+100000*m+1000000*l+10000000*k+100000000*j+1000000000*i)

print(sorted(set(lis))[K])

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

const long long MOD = (long long)(1e9 + 7);
const int kK = (int)(2049 * 2049);

long long fac[kK + 5], inv[kK + 5];

long long qpow(long long base,int power)
{
	long long ret = 1;
	for(; power; power >>= 1)
	{
		if(power & 1) ret = ret * base % MOD;
		base = base * base % MOD;
	}
	return ret;
}

inline long long C(int x, int y)
{
	return(((fac[y] * inv[x]) % MOD) * inv[y - x]) % MOD;
}

int n, k;
long long f[2049][2049];

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	if(k == 1)
	{
		cout << 1 <<endl;
		return 0;
	}
	fac[0] = 1;
	for(int i = 1; i <= kK; ++i) fac[i] = fac[i-1] * i % MOD;
	inv[kK] = qpow(fac[kK], MOD - 2);
	for(int i = kK; i >= 1; --i) inv[i - 1] = inv[i] * i % MOD;
	f[0][0] = 1;
	for(int i = 1;i <= n; ++i)
	{
		f[i][0] = f[i - 1][0];
		for(int j = 1; j <= i; ++j)
		{
			f[i][j] = f[i - 1][j];
			f[i][j] = f[i][j] + f[i][j - 1] * C(k - 2, n * k - i - (j - 1)*(k - 1) - 1);
			f[i][j] %= MOD;
		}
	}
	cout << fac[n] * f[n][n] % MOD<<endl;
	
	return 0;
}

Measured memory_bytes: 97152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) ll(i.size())
#define FOR(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (ll i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

template<class T> inline bool cmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool cmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MOD=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll MAXN=1e5+5;
const ll MAXLG=__lg(MAXN)+2;

ll n,w;
ll v[MAXN],c[MAXN];
ll dp[MAXN];
/********** Good Luck :) **********/
int main()
{
    IOS();
    cin >> n >> w;
    REP (i,n) {
        cin >> c[i] >> v[i];
    }

    REP (i,n) {
        for (ll j=w;j>=0;j--) {
            if (j-c[i] >= 0) {
                dp[j] = max(dp[j],dp[j-c[i]]+v[i]);
            }
        }
    }

    ll ans = 0;
    REP (i,w+1) {
        ans = max(ans,dp[i]);
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  int N;
  cin >> N;
  vector<ll> T(N), A(N);
  for (int i = 0; i < N; i++)
    cin >> T[i] >> A[i];
  for (int i = 0; i < N - 1; i++)
  {
    ll tm = T[i] / T[i + 1];
    ll am = A[i] / A[i + 1];
    ll m = 0;
    if (tm > am)
    {
      m = tm;
      if (T[i] % T[i + 1])
        m++;
    }
    else
    {
      m = am;
      if (A[i] % A[i + 1])
        m++;
    }
    ll t = T[i + 1] * m;
    ll a = A[i + 1] * m;
    T[i + 1] = t;
    A[i + 1] = a;
  }
  cout << T[N - 1] + A[N - 1] << endl;
  return 0;
}


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

using namespace std;

using bellman_cost = long long;
template<class V, class E>
struct Graph
{
	int sz;
	vector<V> v;
	vector<vector<E>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = V(args...);
	}
	// from, to, cost
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

template<class T>
struct Vertex
{
	T cost;
	bool valid = false; // 到達不能または無限にコストが減るときfalse
	Vertex(T v1) : cost(v1) {}
	Vertex() {}
};
using vertex = Vertex<bellman_cost>;

template<class T>
struct Edge
{
	int to;
	T cost;
	Edge(int t, T c) : to(t), cost(c) {}
	Edge() {}
};
using edge = Edge<bellman_cost>;
using graph = Graph<vertex, edge>;

struct Bellmanford : public graph {
	Bellmanford(int n) : graph(n) {};
	void Bellman_solve(int s, bellman_cost INF_COST) {
		for (auto& vv : v) vv.cost = INF_COST, vv.valid = false;
		v[s].cost = 0, v[s].valid = true;
		for (int i = 0; i + 1 < (int) v.size(); i++) {
			for (int j = 0; j < (int) v.size(); j++) {
				for (auto& x: e[j]) {
					if (v[j].cost == INF_COST) continue;
					v[x.to].cost = min(v[x.to].cost, v[j].cost + x.cost);
					v[x.to].valid = true;
				}
			}
		}
		auto valid_check = [&](auto f, int pos) {
			if (!v[pos].valid) return;
			v[pos].valid = false;
			for (auto& y: e[pos]) {
				f(f, y.to);
			}
		};
		for (int i = 0; i < (int) v.size(); i++) {
			for (auto& x: e[i]) {
				if (v[i].cost == INF_COST) continue;
				if (v[x.to].cost > v[i].cost + x.cost) {
					valid_check(valid_check, x.to);
				}
			}
		}
	}
};

/*
template<class V, class E>
void Bellmanford(Graph<V, E>& G, int s, bellman_cost INF_COST)
{
}
*/

void ABC137_E() {
	int N, M, P;
	cin >> N >> M >> P;
	Bellmanford B(N);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		B.add_edge(a-1, b-1, P-c);
	}
	B.Bellman_solve(0, LLONG_MAX);
	if (B.v[N-1].valid) {
		cout << max(0LL, -B.v[N-1].cost) << endl;
	} else {
		cout << -1 << endl;
	}
}

int main() {
	ABC137_E();
}

Measured memory_bytes: 640
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int (i)=(a);(i)<(b);++(i))
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cout<<#x<<"="<<(x)<<endl;
#define DBG(v) REP(i, LEN((v))) cout<<(v)[i]<<(i==LEN((v))-1 ? '\n' : ' ')
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef vector<int> vi;
typedef vector<lint> vl;
typedef vector<vector<int>> vii;
typedef vector<vector<lint>> vll;

class DKi {
public:
    int N, Q;
    vi C, ans;
    vii G;
    int cnt = 0;

    void input(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in>>N>>Q;
        C = vi(N, 0);
        ans = vi(N, 0);
        G = vii(N, vi());
        REP(i, N-1){
            int a, b;
            in>>a>>b;
            a--, b--;
            G[a].pb(b), G[b].pb(a);
        }
    }

    void dfs(int s, int p){
        cnt += C[s];
        ans[s] = cnt;
        for(auto u : G[s]){
            if(u==p) continue;
            dfs(u, s);
        }
        cnt -= C[s];
    }

    void solve(std::istream& in, std::ostream& out) {
        input(in, out);
        REP(i, Q){
            int p, x;
            in>>p>>x;
            C[p-1] += x;
        }
        dfs(0, -1);
        REP(i, N) out<<ans[i]<<' ';
        out<<'\n';
    }
};


int main() {
	DKi solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main() {
    int n; cin >>n;
    vector<int> p(n);
    rep(i, n)
        cin >> p.at(i);
    
    int minv = p.at(0);
    int ans = 1;
    for (int i = 1; i < n; i++) {
        minv = min(minv, p.at(i-1));
        if (minv >= p.at(i)) {
            ans++;
            //cout << i << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long INF = 1LL<<60;
int main() {
  int N,K; cin>>N>>K;
  vector<int64_t> M,P;
  P.push_back(0);
  rep(i,N){
    int64_t a; cin>>a;
    if(a<0) M.push_back(-1*a);
    else if(a>0) P.push_back(a);
    else K--;
  }
  M.push_back(0);
  reverse(M.begin(),M.end());
  int a=M.size()-1,b=P.size()-1;
  int64_t ans=INF;
  rep(i,K+1){
    if(i>b||K-i>a) continue;
    ans=min(ans,P.at(i)+M.at(K-i)+min(P.at(i),M.at(K-i)));
  }
  cout<<ans;
}

Measured memory_bytes: 4572
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n,k;
    std::cin >> n >> k;
    int h[100000];
    int cnt=0;
    for (int i = 0; i < n; i++) {
        std::cin >> h[i];
        if(h[i]>=k){
            cnt++;
        }
    }
    std::cout << cnt << std::endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<vector<int>> opendata(N,vector<int>(10));
  vector<vector<int>> valuedata(N,vector<int>(11));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> opendata.at(i).at(j);
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 11; j++) {
      cin >> valuedata.at(i).at(j);
    }
  }
  vector<int> onoff{0,1};
  int ans = -1000000000, value, ccc = 0;
  vector<int> count(N);
  for(int a: onoff) {
    for(int b: onoff) {
      for(int c: onoff) {
        for(int d: onoff) {
          for(int e: onoff) {
            for(int f: onoff) {
              for(int g: onoff) {
                for(int h: onoff) {
                  for(int i: onoff) {
                    for(int j: onoff) {
                      if (ccc == 0){
                        ccc++;
                        break;
                      }
                      value = 0;
                      vector<int> bin{a,b,c,d,e,f,g,h,i,j};
                      for(int k = 0; k < 10; k++) {
                        for(int l = 0; l < N; l++) {
                          if (k == 0) count.at(l) = 0;
                          count.at(l) += opendata.at(l).at(k) * bin.at(k);
                        }
                      }
                      for(int l = 0; l < N; l++) {
                        value += valuedata.at(l).at(count.at(l));
                      }
                      if (value > ans) ans = value;
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256