akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main()
{
    int n, i, four = 0, even = 0, odd = 0;

    scanf("%d", &n);

    int a[n];

    for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i] % 4 == 0)
            four++;
        else if(a[i] % 2 == 0)
            even++;
        else
            odd++;
    }

    if((four + 1 >= odd && even == 0) || (four>= odd && even != 0))
    {
        printf("Yes\n");
    }

    else
    {
        printf("No\n");
    }

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <map>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    set<string> st;
    while(N--) {
        string s;
        cin >> s;
        st.insert(s);
    }


    cout << st.size() << endl;
    return 0;
}


Measured memory_bytes: 19248
#include <iostream>

using namespace std;

int __gcd(int a, int b) { return b ? __gcd(b, a % b) : a; }

int getgcd(int a, int b, int c) {
    return __gcd(a, __gcd(b, c));
}

int main() {
    int k;
    cin >> k;
    long long res = 0;
    for (int a = 1; a <= k; a++) {
        for (int b = 1; b <= k; b++) {
            for (int c = 1; c <= k; c++) {
                res += getgcd(a, b, c);
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 3192
import itertools
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
p=list(itertools.permutations(range(n)))
ans=0
for i in p:
    for j in range(n-1):
        ans+=((l[i[j+1]][0]-l[i[j]][0])**2+(l[i[j+1]][1]-l[i[j]][1])**2)**0.5
print(ans/len(p))

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

char change (char a){
  if (a == 'q') return 'Q';
  if (a == 'w') return 'W';
  if (a == 'e') return 'E';
  if (a == 'r') return 'R';
  if (a == 't') return 'T';
  if (a == 'y') return 'Y';
  if (a == 'u') return 'U';
  if (a == 'i') return 'I';
  if (a == 'o') return 'O';
  if (a == 'p') return 'P';
  if (a == 'a') return 'A';
  if (a == 's') return 'S';
  if (a == 'd') return 'D';
  if (a == 'f') return 'F';
  if (a == 'g') return 'G';
  if (a == 'h') return 'H';
  if (a == 'j') return 'J';
  if (a == 'k') return 'K';
  if (a == 'l') return 'L';
  if (a == 'z') return 'Z';
  if (a == 'x') return 'X';
  if (a == 'c') return 'C';
  if (a == 'v') return 'V';
  if (a == 'b') return 'B';
  if (a == 'n') return 'N';
  if (a == 'm') return 'M';
  if (a == 'Q') return 'Q';
  if (a == 'W') return 'W';
  if (a == 'E') return 'E';
  if (a == 'R') return 'R';
  if (a == 'T') return 'T';
  if (a == 'Y') return 'Y';
  if (a == 'U') return 'U';
  if (a == 'I') return 'I';
  if (a == 'O') return 'O';
  if (a == 'P') return 'P';
  if (a == 'A') return 'A';
  if (a == 'S') return 'S';
  if (a == 'D') return 'D';
  if (a == 'F') return 'F';
  if (a == 'G') return 'G';
  if (a == 'H') return 'H';
  if (a == 'J') return 'J';
  if (a == 'K') return 'K';
  if (a == 'L') return 'L';
  if (a == 'Z') return 'Z';
  if (a == 'X') return 'X';
  if (a == 'C') return 'C';
  if (a == 'V') return 'V';
  if (a == 'B') return 'B';
  if (a == 'N') return 'N';
  if (a == 'M') return 'M';
}
int main() {
 string a, b, c;
 cin >> a >> b >> c;
 
 cout << change(a.at(0)) << change(b.at(0)) << change(c.at(0)) << endl;
}

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

int main(){
    string s;
    cin >> s;

    int g = 0, p = 0, win = 0, lose = 0;
    for(int i = 0; i < s.length(); i++){
        if(g == p){
            g++;
            if(s[i] == 'p') lose++;
        }else if(s[i] == 'g'){
            p++;
            win++;
        }else if(s[i] == 'p'){
            // ここでパーを消費してあいこにするか、グーを出して負けておいてパーを温存するか？
            p++; // パーを消費してあいこにするパターン.
        }
    }

    cout << win-lose << endl;

    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool sortbysec(const pair<int,int> &a,
               const pair<int,int> &b)
{
    return (a.second < b.second);
}
int main()
{
    ll t=1,i,j,k=0,n,z,a,b,d,x,y,m;
    //cin>>t;
    while(t--)
    {
       string s;
       vector<ll>v;
       cin>>s;
       ll cnt=0;
       for(i=0;i<3;i++)
       {
           if(s[i]=='R')
            cnt++;
           else
           {
               v.push_back(cnt);
               cnt=0;
           }
       }
       if(s[2]=='R')
        v.push_back(cnt);
       sort(v.begin(),v.end());
       reverse(v.begin(),v.end());
       cout<<v[0]<<endl;



    }
    return 0;
}


Measured memory_bytes: 3628
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<time.h>
using namespace std;
typedef long long ll;
int n,m,v,p,a[100005],b[100005],ans,pth_min;
bool judge(int pth){
	ll res=0;
	int i;
	for(i=1;i<=n;i++)
		b[i]=min(m,pth-a[i]);
	sort(b+1,b+n+1);
	if(b[p]<0)
		return 0;
	for(i=1;i<=n;i++)
		res+=i<=p-1?m:b[i];
	return res>=(ll)m*v;
}
int solve(){
	int l=0,r=2e9,mid,res=-1;
	while(l<=r){
		mid=((ll)l+r)>>1;
		if(judge(mid))
			r=mid-1,res=mid;
		else
			l=mid+1;
	}
	return res;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&v,&p);
	int i;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	pth_min=solve();
	for(i=1;i<=n;i++)
		ans+=a[i]+m>=pth_min;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 4616
import scala.collection.mutable
import scala.io.StdIn._

sealed abstract class Piece
case object Queen extends Piece
case object Danger extends Piece
case object Empty extends Piece

object Main extends App {
  type Pos = mutable.Seq[mutable.Seq[Piece]]
  val k = readInt()
  val pos: Pos = mutable.Seq.fill(8, 8)(Empty)

  val next = List(
    (r: Int, c: Int) => (r - 1, c),
    (r: Int, c: Int) => (r + 1, c),
    (r: Int, c: Int) => (r, c - 1),
    (r: Int, c: Int) => (r, c + 1),
    (r: Int, c: Int) => (r - 1, c - 1),
    (r: Int, c: Int) => (r - 1, c + 1),
    (r: Int, c: Int) => (r + 1, c - 1),
    (r: Int, c: Int) => (r + 1, c + 1)
  )

  for (i <- 1 to k) {
    val Array(r, c) = readLine().split(" ").map(_.toInt)
    pos(r)(c) = Queen
    next.foreach(f => {
      var row = r
      var col = c
      while (isOnBoard(row, col)) {
        if (pos(row)(col) == Empty) pos(row)(col) = Danger
        val n = f(row, col)
        row = n._1
        col = n._2
      }
    })
  }

  solve(0)

  pos.foreach(r => {
    r.foreach {
      case Queen => print("Q")
      case _ => print(".")
    }
    println
  })

  def isOnBoard(r: Int, c: Int): Boolean = 0 <= r && r <= 7 && 0 <= c && c <= 7

  def isSafe(r: Int, c: Int): Boolean = {
    next foreach (f => {
      var row = r
      var col = c
      while (isOnBoard(row, col)) {
        if (pos(row)(col) == Queen) return false
        val n = f(row, col)
        row = n._1
        col = n._2
      }
    })
    true
  }

  def solve(r: Int): Boolean = {
    if (pos(r) contains Queen) {
      if (r == 7) return true
      else return solve(r + 1)
    }

    for (c <- pos(r).indices) {
      if (pos(r)(c) == Empty && isSafe(r, c)) {
        pos(r)(c) = Queen
        if (r == 7 || solve(r + 1)) return true
        else pos(r)(c) = Empty
      }
    }
    false
  }
}

Measured memory_bytes: 44620
while 1:
    n=input()
    if n==0:break
    ascore=0
    bscore=0
    for i in xrange(n):
        a,b=map(int,raw_input().split())
        if a>b:
            ascore+=a+b
        elif a==b:
            ascore+=a
            bscore+=b
        else:
            bscore+=a+b
    print ascore,bscore

Measured memory_bytes: 6372
const input=require('fs').readFileSync('/dev/stdin', 'utf8').split(/[\s]/);const nin=()=>{const r = input[0];input.shift();return Number(r)};const nrin=(n)=>{const a:number[]=[];rep(n,()=>a.push(nin()));return a};const sin=()=>{const r = input[0];input.shift();return String(r)};const out=(...a)=>{console.log(...a)};const floor=(a)=>{return Math.floor(a)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const rep=(n, callback)=>{for(let i = 0;i < n; i++){callback()}};const strrep=(s, i, v)=>{return s.slice(0, i)+v+s.slice(i+1);};const permutation=({result=[],pre=[],post,n=post.length})=>{if(n>0){post.forEach((_,i)=>{const rest=[...post];const elem=rest.splice(i, 1);permutation({result, pre: [...pre,...elem],post:rest,n:n-1})})}else{result.push(pre)}return result};const sw=(s,a:any[])=>{for(let i=0;i<a.length;i+=2)if(s==a[i])return a[i+1]};const or=(a,...b)=>{for(let i=0;i<b.length;i++)if(a==b[i])return true;return false};const maxindex=(...a)=>{return a.indexOf(Math.max.apply(null,a))};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{return ar.sort((a,b)=>{return b-a})};
const main = ()=>{
  let n=nin()
  let [...a]= asc(nrin(n));
  if(a[n/2-1] == a[n/2]) out(0)
  else out(a[n/2] - a[n/2-1]);
}
main();

Measured memory_bytes: 26684
object Main extends App {
  def getGcd(a: Int, b: Int): Int = {
    (1 to math.min(a, b))
      .find(e => e != 1 && a % e == 0 && b % e == 0)
      .map(common => common * getGcd(a / common, b / common))
      .getOrElse(1)
  }
  Stream
    .continually(readLine)
    .takeWhile(_ != null)
    .map(_.split(" ").map(_.toInt))
    .map {
      case Array(a, b) =>
        val gcd: Int = getGcd(a, b)
        Seq(gcd, math.max(a, b) / gcd * math.min(a, b)).mkString(" ")
    }
    .foreach(println)
}



Measured memory_bytes: 44484
#include <iostream>
#include <string>
#include <vector>

int main()
{
	std::string str;
	std::cin >> str;

	std::vector<std::string> days = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT" };
	
	for (int i = 0; i < days.size(); ++i)
	{
		if (str == days[i])
		{
			std::cout << 7 - i << std::endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define null NULL
#define mp make_pair
#define pb(a) push_back(a)
#define sz(a) ((int)(a).size())
#define all(a) a.begin() , a.end()
#define fi first
#define se second
#define relaxMin(a , b) (a) = min((a),(b))
#define relaxMax(a , b) (a) = max((a),(b))
#define SQR(a) ((a)*(a))
#define PI 3.14159265358979323846
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

const int MAX = 410;

int par[SQR(MAX)];

int GetPar(int vr){
  return par[vr] == vr ? vr : par[vr] = GetPar(par[vr]);
}

void Merge(int a, int b){
  a = GetPar(a);
  b = GetPar(b);
  par[a] = b;
}

int h, w;
char in[MAX][MAX];
int id[MAX][MAX];

vector<pii> dlt = {mp(-1, 0), mp(+1, 0),
                   mp(0, -1), mp(0, +1)};

int main(){
  for(int i = 0;i < SQR(MAX);++i) par[i] = i;

  scanf("%d%d", &h, &w);
  for(int i = 0;i < h;++i)
    scanf("%s", in[i]);

  for(int i = 0, t = 0;i < h;++i)
    for(int j = 0;j < w;++j)
      id[i][j] = t++;

  for(int i = 0;i < h;++i)
    for(int j = 0;j < w;++j)
      for(const auto& d : dlt){
        int ii = i + d.fi;
        int jj = j + d.se;
        if(ii >= 0 && jj >= 0 &&
           ii < h && jj < w &&
           in[i][j] != in[ii][jj]){
          Merge(id[i][j], id[ii][jj]);
        }
      }

  vector<pair<ll, ll>> ans(w * h);
  for(int i = 0;i < h;++i)
    for(int j = 0;j < w;++j)
      if(in[i][j] == '.') ++ans[GetPar(id[i][j])].fi;
      else ++ans[GetPar(id[i][j])].se;

  ll total = 0;
  for(int i = 0;i < w * h;++i)
    total += ans[i].fi * ans[i].se;

  cout << total << '\n';

  return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printv(x) for(int i = 0; i < x.size(); i++){ cout << (x[i]) << " "; } cout << endl; 
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printaa(x) for(int i = 0; i < (sizeof(x)/sizeof(x[0])); i++){ for(int j = 0; j < (sizeof(x[0])/sizeof(x[0][0])); j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,i;
    cin >> N >> i;
    print(N-i+1);
}


Measured memory_bytes: 256
//Atcoder solution
#include<iostream>
using namespace std;

void solve(int a,int b,int c)
{
  int sum;
  sum=a+b+c;

  if(sum>=22)
  {
  	cout<<"bust"<<endl;
  }
  else
  	cout<<"win"<<endl;
}
int main()
{
  int a,b,c;
  cin>>a>>b>>c;

  solve(a,b,c);
}

Measured memory_bytes: 2988
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

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

	int n;
	cin >> n;
	string name;
	long long count[5] = {};
	long long pattern = 0;
	for (int i = 0; i < n; i++) {
		cin >> name;
		if (name.find("M") == 0) {
			count[0]++;
		}
		if (name.find("A") == 0) {
			count[1]++;
		}
		if (name.find("R") == 0) {
			count[2]++;
		}
		if (name.find("C") == 0) {
			count[3]++;
		}
		if (name.find("H") == 0) {
			count[4]++;
		}
	}
	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 5; j++) {
			for (int k = j + 1; k < 5; k++) {
				pattern += count[i] * count[j] * count[k];
			}
		}
	}
	cout << pattern << "\n";
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{

	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		public FastReader(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		public String next(){
			try{
				while(st==null||!st.hasMoreElements()){
					st = new StringTokenizer(br.readLine());
				}
			}catch(Exception e){
				e.printStackTrace();
			}
			return st.nextToken();
	
		}
		public int nextInt(){
			return Integer.parseInt(next());
		}
		public long nextLong(){
			return Long.parseLong(next());
		}
		public double nextDouble(){
			return Double.parseDouble(next());
		}
		public String nextLine(){
			String s = "";
			try{
				s = br.readLine();
			}catch(Exception e){
				e.printStackTrace();
			}	
			return s;		
		}
	} 
	
	public static void main(String[] args){
		FastReader in = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		long n = in.nextLong();
		long m = in.nextLong();
		long ans;
		if(n>=m/2){
			ans = m/2;
		}
		else{
			
			ans = (n+m/2)/2;
		}
		out.println(ans);		
		out.flush();
		out.close();  
	}

}





Measured memory_bytes: 21204
#include "bits/stdc++.h"

using namespace std;

int main() {
	int N, K;
	cin >> N >> K ;
	vector<int>A(N);//初期パワー
	for (int n = 0;n< N;++n) {
		cin >> A[n];
	}
	for (int n = 0; n < K; ++n) {
		bool end = true;
		vector <int >B(N);
		for (int i = 0;i < N; ++i){
			//累積和
			int l = max(0, i - A[i]);
			int r = min(N - 1, i + A[i]);
			B[l]++;
			if (r+1<N) {
				B[r + 1]--;
			}
		}
		for (int i =1;i < N;++i){
			B[i] += B[i - 1];
			if (N != B[i]) {
				end = false;
			}
		}
		A = B;
		if (end) {
			break;
		}
	}

	for (int n = 0; n < N; ++n) {
		cout << A[n];
		if (n != N-1) {
			cout << " ";
		}
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 4848
#include"bits/stdc++.h"

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF * 300 * 300;
const int MOD = 1e9+7;

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

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;
}


void Main()
{
    string s;cin>>s;
    int n = SIZE(s);
    int result = INF;

    int t1 = 0;
    bool w1 = false;
    bool b1 = false;
    REP(i,n){
        if(i!=0 && s[i]==s[i-1]){
            continue;
        }
        if(s[i]=='B'){
            if(w1){
                t1++;
            }
            b1 = true;
        }
        if(s[i]=='W'){
            if(b1){
                t1++;
            }
            w1 = true;
        }
    }
    result = min(result,t1);

    int t2 = 0;
    bool w2 = false;
    bool b2 = false;
    PER(i,n){
        if(i!=n-1 && s[i]==s[i+1]){
            continue;
        }
        if(s[i]=='B'){
            if(w2){
                t2++;
            }
            b2 = true;
        }
        if(s[i]=='W'){
            if(b2){
                t2++;
            }
            w2 = true;
        }
    }
    result = min(result,t2);

    cout<<result<<endl;



	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

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

const ll INF = 1LL << 60;

ll N;
vector<ll> A;

// 最大公約数
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

// 最小公倍数
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }

vector<pair<ll, ll>> prime_factorize(ll n) {
    vector<pair<ll, ll>> res;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

const int mod = 1e9 + 7;

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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
    cin >> N;
    A.resize(N);
    rep(i, N) cin >> A[i];

    map<ll, ll> mp;

    rep(i, N) {
        vector<P> v = prime_factorize(A[i]);
        map<ll, ll> tmp;
        rep(j, v.size()) {
            if (mp[v[j].first] < v[j].second) {
                mp[v[j].first] = v[j].second;
            } 
            tmp[v[j].first] = v[j].second;
        }
    }

    // for (auto m : mp) {
    //     cout << m.first << " " << m.second << endl;
    // }

    // 最小公倍数を素因分解されているものが求まった
    mint lcm = 1;
    for (auto m : mp) {
        lcm *= powl(m.first, m.second);
    }

    mint ans = 0;
    rep(i, N) {
        ans += lcm / A[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 4320
#include "bits/stdc++.h"

using namespace std;

int stmp[100010];
int gtmp[100010];

int main()
{
    long long mod=1000000007;
    int n;
    cin >> n;
    string s,g;
    cin >> s >>g;
    for(int i=0;i<n;i++){
        stmp[i]=s[i]-'a';
        gtmp[i]=g[i]-'a';
    }
    long long al[26]={};
    long long dp[n]={};
    al[stmp[0]]=1;
    dp[0]=1;
    for(int i=1;i<n;i++){
        dp[i]=(al[gtmp[i]]%mod);
        al[stmp[i]]+=(dp[i]%mod);
    }
    cout << dp[n-1]<< endl;
    return 0;
}



Measured memory_bytes: 4824
n = int(input())
an = list(map(int, input().split(' ')))

neg = [ai for ai in an if ai < 0]

sum = 0
mini = 10 ** 9
for ai in an:
  sum += abs(ai)
  mini = min(mini, abs(ai))
  
if len(neg) % 2 != 0:
  sum -= 2 * mini

print(sum)


Measured memory_bytes: 14412
#include <bits/stdc++.h>
typedef long long int lld;
typedef unsigned long long int llu;
#define INF (lld)(9223372036854775807)
#define IINF (int)(2147483647)

using namespace std;

int main(void) {
  lld n;
  cin >> n;
  vector<lld> a(n);
  lld s = 0;
  for (lld i = 0; i < n; i++) {
    cin >> a[i];
    s ^= a[i];
  }
  for (lld i = 0; i < n; i++) {
    cout << (a[i] ^ s) << (i == n - 1 ? "\n" : " ");
  }
}

Measured memory_bytes: 4836
#include<stdio.h>

int main()
{
  int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;
  scanf("%d",&k);
  printf("%d",a[k-1]);
}


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

int main(){
  int n, a, b, c, tmp;
  int sum;
  string str;
  int i;

  while(cin>>n){
    if(n==0) break;
    sum=1; a=1; b=2, c=3;
    for(i=0; i<n; i++){
      cin>>str;
      switch(str[0]){
      case 'N':
        tmp=a; a=b; b=7-tmp; break;
      case 'S':
        tmp=a; a=7-b; b=tmp; break;
      case 'E':
        tmp=a; a=7-c; c=tmp; break;
      case 'W':
        tmp=a; a=c; c=7-tmp; break;
      case 'R':
        tmp=b; b=c; c=7-tmp; break;
      case 'L':
        tmp=b; b=7-c; c=tmp; break;
      }
      sum+=a;
    }
    printf("%d\n", sum);
  }

  return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> n(N);
  for(int i=0;i<N;i++){
    n.at(i)=i+1;
  }
  long long int ans=0;
  for(int i=0;i<N;i++){
    if(n.at(i)%3==0||n.at(i)%5==0||n.at(i)%15==0){
      ans=ans;
    }
    else ans=ans+n.at(i);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 7128
module CharMap = Map.Make (Char)

let () =
  let s = read_line () in
  Array.init (String.length s) (fun i -> i, s.[i])
  |> Array.fold_left (fun m (i, c) ->
      CharMap.add c (i :: try CharMap.find c m with Not_found -> []) m) CharMap.empty
  |> CharMap.bindings
  |> List.map (fun (_, is) ->
      List.map (fun i ->
        Array.init 5 (fun n ->
          try [String.init (n + 1) (fun j -> s.[i + j])]
          with _ -> [])
        |> Array.to_list
        |> List.concat) is |> List.concat)
  |> List.concat
  |> List.sort_uniq compare
  |> Scanf.scanf "%d\n" (fun k l -> List.nth l (k - 1))
  |> print_endline

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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

//拡張ユークリッドの互除法
int extgcd(int a, int b, int& x, int& y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

// mod逆元
int mod_inverse(int a, int m) {
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

int N, A, B, K;
int fact[330000], fact_inv[330000];
int mod = 998244353;

signed main() {
    cin >> N >> A >> B >> K;
    fact[0] = fact_inv[0] = 1;
    for (int i = 1; i < 330000; i++) {
        fact[i] = fact[i - 1] * i % mod;
        fact_inv[i] = mod_inverse(fact[i], mod);
    }
    int ans = 0;
    for (int i = 0; i <= N; i++) {
        if ((K - A * i >= 0) && (K - A * i) % B == 0 && (K - A * i) / B <= N) {
            int j = (K - A * i) / B;
            cerr << i << " " << j << endl;
            (ans += fact[N] * fact_inv[i] % mod * fact_inv[N - i] % mod * fact[N] % mod * fact_inv[j] % mod * fact_inv[N - j] % mod) %= mod;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 5376
#include<stdio.h>
#define min(a,b) (((a)<(b))?(a):(b))
#define INF 10000000

int cost[100][500];
int mincost[500];
int used[500];

int main(void)
{
	int n, m,a,b,c;
	int i,j;
	while (1) {
		scanf("%d %d", &n, &m);
		if (n == 0 && m == 0)break;
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (i == j)cost[i][j] = 0;
				else
					cost[i][j] = INF;
			}
		}
		for (i = 0; i < m; i++) {
			scanf("%d %d %d", &a, &b, &c);
			cost[a][b] = c;
			cost[b][a] = c;
		}

		for ( i = 0; i < n; i++) {
			mincost[i] = INF;
			used[i] = 0;
		}
		mincost[0] = 0;
		int res = 0;

		while (1) {
			int v = -1;
			int u;
			for (u = 0; u < n; u++) {
				if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
			}
			if (v == -1)break;
			used[v] = 1;
			res += mincost[v];

			for (u = 0; u < n; u++)
				mincost[u] = min(mincost[u], cost[v][u]);
		}
		printf("%d\n",res);
	}
	return 0;
}

Measured memory_bytes: 796
import math

N,D = map(int, input().split())
idx = [list(map(int, input().split())) for i in range(N)]
count = 0
Sum = 0

for i in range(N-1):
    for j in range(i+1,N):
        for k in range(D):
            Sum = Sum + (idx[i][k]-idx[j][k])**2 
        distance = math.sqrt(Sum)
            
        if distance == round(distance):
            count += 1
        Sum = 0

print(count)

Measured memory_bytes: 3064
a,b = gets.chomp.split(" ").map(&:to_i)
s = gets.chomp
arr = 10.times.map(&:to_s)

if s[a] == "-"  then
  (s[0..(a-1)] + s[(a+1)..-1]).each_char do |c|
    unless arr.include?(c) then
      puts "No"
      exit
    end
  end
  puts "Yes"
else
  puts "No"
end



Measured memory_bytes: 1788
#include <cstdio>
#include <cstdlib>
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=100005,mod=1e9+7;
void print(int x){printf("%d\n",x);exit(0);}
int n,m,l,res,a[N],cnt,head[N],h[N],w[N*2],p[N],f[N];bool b[N],vis[N];
struct edge{int to,nxt;}e[N];
void add(int x,int y){e[++cnt]=(edge){y,head[x]};head[x]=cnt;}
int dfs(int f,int x){
	vis[x]=1;
	int Y=0,t=0;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;if(y!=f)Y=y,t++;
	}
	if(t>1)return 0;
	if(t==0)return 1;
	int s=dfs(x,Y);if(s)++s;
	return s;
}
int main(){
	scanf("%d",&n);
	ref(i,1,n)scanf("%d",&a[i]),add(a[i],i);
	res=1;
	ref(i,1,n)if(!vis[i]){
		m=l=0;
		for(int x=i;;b[x]=1,x=a[x]){
			h[++m]=x;if(b[x])break;
		}
		bool fg=0;
		for(int x=m;x==m||h[x]!=h[m];x--){
			w[++l]=dfs(h[x-1],h[x]);
			if(!w[l])print(0);w[l]--;
		}
		ref(i,1,l)w[i+l]=w[i];
		ref(i,1,l)if(w[i]){
			fg=1;int tt=0;
			ref(j,i+1,2*l)if(!w[j])tt++;else break;
			if(tt<w[i]-1)print(0);
			if(tt>w[i]-1)(res*=2)%=mod;
		}
		if(!fg)p[l]++;
	}
	ref(i,1,n)if(p[i]){
		f[0]=1;if((i&1)&&i>1)f[1]=2;else f[1]=1;
		if((i&1)&&i>1) ref(j,2,p[i])f[j]=(1LL*f[j-2]*(j-1)%mod*i+2*f[j-1])%mod;
		else ref(j,2,p[i])f[j]=(1LL*f[j-2]*(j-1)%mod*i+f[j-1])%mod;
		res=1LL*res*f[p[i]]%mod;
	}
	print(res);
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i = n;i >= 0;--i)
#define FOR(i,m,n) for(int i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

ll mod_factorial(ll n,ll mod)
{
    ll k = 1;
    for(ll i = 1; i<= n;i++){
        k = (k * (i %mod))%mod;
    }
    return k;
}

int main(void)
{
    ll x,y;
    ll mod = 1e9+7;
    
    cin >> x >> y;
    
    if((2*x - y)%3 == 0 && (2*y-x)%3 == 0 && 2*x-y >= 0 && 2*y - x >= 0){
        ll a = (2*x-y)/3;
        ll b = (2*y - x)/3;
        cout << ((mod_factorial(a + b ,mod) *modinv(mod_factorial(a,mod),mod)%mod)*modinv(mod_factorial(b,mod),mod))%mod << endl;
    }
    else{
        cout << 0 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const double EPS  = 1e-10;
const bool debug = 0;

int main(){
	int e[4];
	REP(i, 4) scanf("%d", e + i);
	sort(e, e + 4);
	
	if (e[0] == e[1] && e[2] == e[3]) puts("yes");
	else puts("no");
	
	return 0;
}

Measured memory_bytes: 3184
import numpy as np
n, m, c = map(int, input().split(' '))
b = np.array(list(map(int, input().split(' '))))
a = []
for i in range(n):
    a.append(np.array(list(map(int, input().split(' ')))))

count = 0
for nn in range(len(a)):
    if np.sum(a[nn] * b) + c > 0:
        count += 1
print(count)


Measured memory_bytes: 21780
#include <bits/stdc++.h>
using namespace std;
const int N=220000;
const int P=1000000007;
long long sum[N];
int n,k,ans;
int main(){
	scanf("%d%d",&n,&k);
	
	sum[0]=0;
	for(int i=1;i<=n;++i)sum[i]=sum[i-1]+i;
	
	ans=0;
	for(int i=k;i<=n;++i)ans=(1ll*ans+sum[n]-sum[n-i]-sum[i-1]+1)%P;
	
	printf("%d\n",(ans+1)%P);
	
	return 0;
}

Measured memory_bytes: 5320
#include<cstdio>
#include<iostream>
#include <algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
int ship[25][25];

int n,m;
int t,k;
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d",&k,&t);
    for(int j=1;j<=k;j++)
    {
        for(int i=1;i<=m;i++)
            ship[j][i]=1;
    }
    for(int j=1;j<=t;j++)
    {
        for(int i=1;i<=n;i++)
            ship[i][j]=1;
    }
    int tot=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!ship[i][j]) tot++;

    cout<<tot<<endl;
    return 0;
}


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

int main() {
    int x, dig;
    cin >> x;
    for(int i =0; i<3; i++){
        dig = x % 10;
        if (dig == 7){
            cout << "Yes";
            return 0;
        }
        x = x / 10;
    }
    cout << "No";
    return 0;
}


Measured memory_bytes: 3104
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int **dp[128][128], part[128][128];
char str[128][128];

int calc (int x, int y, int a, int b)
{
    return part[a][b] - part[a][y - 1] - part[x - 1][b] + part[x - 1][y - 1];
}

int main ()
{
   // freopen ("file.in", "r", stdin);

    int n, m;
    scanf ("%d %d\n", &n, &m);

    int x, y;
    for (int i = 1; i <= n; ++i)
    {
        fgets (str[i] + 1, 128, stdin);

        for (int j = 1; j <= m; ++j)
        {
            part[i][j] = part[i - 1][j] + part[i][j - 1] - part[i - 1][j - 1] + (str[i][j] == 'o');
            if (str[i][j] == 'E') x = i, y = j;
        }
    }

    for (int i = 0; i <= y + 1; ++i)
        for (int j = 0; j <= m - y + 2; ++j)
        {
            dp[i][j] = new int* [x + 5];

            for (int h = 0; h <= x + 3; ++h)
            {
                dp[i][j][h] = new int [n - x + 2];
                for (int k = 0; k <= n - x; ++k)
                    dp[i][j][h][k] = 0;
            }
        }

    for (int l = 0; l <= y - 1; ++l)
        for (int r = 0; r <= m - y; ++r)
            for (int u = 0; u <= x - 1; ++u)
                for (int d = 0; d <= n - x; ++d)
                {
                    if (y + r + 1 < m - l + 1) dp[l][r + 1][u][d] = max (dp[l][r + 1][u][d], dp[l][r][u][d] + calc (max (x - u, d + 1), y + r + 1, min (x + d, n - u), y + r + 1));
                    else dp[l][r + 1][u][d] = max (dp[l][r + 1][u][d], dp[l][r][u][d]);

                    if (y - l - 1 > r) dp[l + 1][r][u][d] = max (dp[l + 1][r][u][d], dp[l][r][u][d] + calc (max (x - u, d + 1), y - l - 1, min (x + d, n - u), y - l - 1));
                    else dp[l + 1][r][u][d] = max (dp[l + 1][r][u][d], dp[l][r][u][d]);

                    if (x + d + 1 < n - u + 1) dp[l][r][u][d + 1] = max (dp[l][r][u][d + 1], dp[l][r][u][d] + calc (x + d + 1, max (y - l, r + 1), x + d + 1, min (y + r, m - l)));
                    else dp[l][r][u][d + 1] = max (dp[l][r][u][d + 1], dp[l][r][u][d]);

                    if (x - u - 1 > d) dp[l][r][u + 1][d] = max (dp[l][r][u + 1][d], dp[l][r][u][d] + calc (x - u - 1, max (y - l, r + 1), x - u - 1, min (y + r, m - l)));
                    else dp[l][r][u + 1][d] = max (dp[l][r][u + 1][d], dp[l][r][u][d]);
                }

    printf ("%d\n", dp[y - 1][m - y][x - 1][n - x]);

    return 0;
}


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

#define EB emplace_back
#define int long long
#define F first
#define S second
#define N 500005
#define all(x) x.begin(),x.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

int32_t main(){
	IOS;
	int tt = 1; 
	//cin >> tt;
	while(tt--){
		int n; cin >> n;
		int sum = 0;
		map<int,int> mp;
		for(int i = 0; i < n; i++){
			int x; cin >> x;
			mp[x]++;
			sum += x;
		}
		int q; cin >> q;
		while(q--){
			int a,b; cin >> a >> b;
			sum -= mp[a] * a;
			sum += mp[a] * b;
			mp[b] += mp[a];
			mp[a] = 0;
			cout << sum << endl;
		}	
	}
	return 0;
}


Measured memory_bytes: 9448
from collections import defaultdict

N, M = map(int, input().split())
P, Y = [], []
ylist = defaultdict(list)
pset = set()
for i in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
    ylist[p].append(y)
    pset.add(p)

cdict = defaultdict(dict)
for p in pset:
    syear = sorted(ylist[p])
    for i, y in enumerate(syear):
        cdict[p][y] = i + 1

for i in range(M):
    p = P[i]
    y = Y[i]
    rank = cdict[p][y]
    print('{:06}{:06}'.format(p, rank))


Measured memory_bytes: 123608
#include<bits/stdc++.h>
#define eps 1e-9
#define MOD 998244353
#define INV_10 299473306
#define INF 1000000000
using namespace std;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	n%=10;
	if(n==3)
		cout << "bon\n";
	else if(n==1||n==0||n==6||n==8)
		cout << "pon\n";
	else
		cout << "hon\n";
}

Measured memory_bytes: 3640
import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		if (a<b) {
			System.out.println("a < b");
		}else if(a==b) {
			System.out.println("a == b");
		}else {
			System.out.println("a > b");
		}
	}

}



Measured memory_bytes: 26304
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int main()
{
   double n,p;
   double s=0.0;
   cin>>n;
   for(ll i=0;i<n;i++)
   {
       cin>>p;
       s+=double(1/p);
     //  cout<<double(1/p);
   }
   double dd=1/s;
   cout<<dd;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;

int main()
{
  ll n,m;
  ll i;
  ll ans=0;
  
  scanf("%lld%lld",&n,&m);
  
  for(i=1;i*i<=m;++i){
    if(m%i==0&&m/i>=n&&ans<i){
      ans=i;
    }
    ll ii=m/i;
    if(m%ii==0&&m/ii>=n&&ans<ii){
      ans=ii;
    }
  }
  
  printf("%lld",ans);
  return 0;
}
 

Measured memory_bytes: 128
#include<stdio.h>
#define INFINITY 1000000000
int count=0;
void merge(int A[],int left,int mid,int right){
  int n1,n2,i,k,j;
  n1=mid-left;
  n2=right-mid;

  int l[n1+1],r[n2+1];

  for(i=0;i<n1;i++)l[i]=A[left+i];
  for(i=0;i<n2;i++)r[i]=A[mid+i];
  l[n1]=INFINITY;
  r[n2]=INFINITY;
  i=j=0;
  count+=right-left;
  for(k=left;k<right;k++){
    if(l[i]<=r[j]){
      A[k]=l[i];
      i+=1;
    }
    else {
      A[k]=r[j];
      j+=1;
    }

  }
}

void mergesort(int A[],int left,int right){

  int mid,i=0;
  if(left+1<right){
    mid=(left+right)/2;
    mergesort(A,left,mid);
    mergesort(A,mid,right);
    merge(A,left,mid,right);
  }
}

int main(){
  int n,s[500000],i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
  mergesort(s,0,n);
  for(i=0;i<n-1;i++){
    printf("%d ",s[i]);
  }
  printf("%d\n%d\n",s[n-1],count);
  return 0;
}



Measured memory_bytes: 5600
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	int x, n;
	std::cin >> x >> n;

	std::vector<int> p(n);
	for (int i = 0; i < n; ++i)
		std::cin >> p[i];

	int minD = 1000;
	int result = 0;
	for (int j = 200; j > -100; --j)
	{
		if (std::any_of(p.begin(), p.end(), [j](int v) { return j == v; })) continue;
		
		if (minD >= std::abs(j - x))
		{
			minD = std::abs(j - x);
			result = j;
		}
	}

	std::cout << result << std::endl;

	return 0;
}

Measured memory_bytes: 3644
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))

Measured memory_bytes: 66396
# -*- coding: utf-8 -*-

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

X = int(input())

if X == 2:
    print(X)
    sys.exit()

if X%2 == 0:
    tmp = X + 1
else:
    tmp = X

for i in range(50000):
    if is_prime(tmp):
        print(tmp)
        sys.exit()
    else:
        tmp = tmp + 2

Measured memory_bytes: 64492
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x:x[1],reverse=True)  
for b, c in BC:
  A.extend([c] * b)
  if len(A)>=2*N:
    break
A = sorted(A, reverse=True)
print(sum(A[:N]))

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

int calc_sum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int sum = calc_sum(i);
        if (sum >= a && sum <= b) {
            res += i;
        }
    }
    cout << res << endl;
    return 0;
}


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

const int N=1e5+5;
int A[N],B[N];
bool used[N];
int main() {
    int n;
    cin >> n;
    REP(i,n) cin >> A[i] >> B[i];
    vector<array<int,2>> a;
    REP(i,n) {
        a.push_back({A[i]+B[i],i});
    }
    sort(a.begin(),a.end());
    long long sum=0;
    REP(i,n) {
        while ( used[a.back()[1]] ) a.pop_back();
        int j=a.back()[1];
        used[j]=1;
        a.pop_back();
        if ( i%2 ) {
            sum-=B[j];
        } else {
            sum+=A[j];
        }
    }
    cout << sum << '\n';
    return 0;
}



Measured memory_bytes: 5040
#include<bits/stdc++.h>
using namespace std;
long long n,m;
int main()
{
	cin>>n>>m;
	for(int i=m/n;i>=1;i--)
	   {
	   	if(m%i==0)
	   	{
		    cout<<i;
	   		return 0;
		   }
	   }
	
}

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

int main(){
int n;
int r;
cin >> n >> r;
while (n!=0 || r!=0){
vector<int> card(n+1);
for (int i = 0; i < n; i++){
card[i]=n-i;
}
for (int i = 0; i < r; i++){
int p;
int c;
cin >> p >> c;
for (int j = 0; j < c; j++){
int deletenumber;
deletenumber = card[c+p-2];
card.erase(card.begin() + c+p-2);
card.insert(card.begin(),deletenumber);
}
}
cout << card[0] << endl;
cin >> n >> r;
}
}


Measured memory_bytes: 2988
/*  -*- coding: utf-8 -*-
 *
 * 2916.cc: Twins
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  char s[8];
  scanf("%s", s);

  if (s[0] == 'a') puts("square1001");
  else puts("e869120");
  return 0;
}



Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
// -----------------<fast IO>------------------
#define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FLSH             fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x)     cout << fixed << setprecision(x);
// -----------------<TypeDef Start>------------------
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
// -----------------<Constants>------------------
const int MAXN = 1000005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);

const int INF=1e9;

int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;
/*ll gcd(ll a,ll b)
{
    if(a==0)
    return(b);
    return(gcd(b%a,a));
}*/
// --------------------------------------------------</TEMPLATE>--------------------------------------------------
ll arr[505][505];
ll brr[505][505];
void solve()
{
    string s1,s2;
    cin>>s1>>s2;
    ll n=s1.length(),m=s2.length();
    ll dp[n+1][m+1];
    for(ll i=0;i<n+1;i++)
    {
        for(ll j=0;j<m+1;j++)
        {
            if(i==0 || j==0)
                dp[i][j]=0;
            else if(s1[i-1]==s2[j-1])
                dp[i][j]=1+dp[i-1][j-1];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    ll i=n,j=m;
    string ans;
    while(i>0 && j>0)
    {
        if(s1[i-1]==s2[j-1])
        {
            ans+=s1[i-1];
            i--;
            j--;
        }
        else if(dp[i-1][j]>dp[i][j-1])
            i--;
        else
            j--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
}

int main()
{
    IOS
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return(0);
}


Measured memory_bytes: 73960
#include <stdio.h>

int main()
{
	long long N, K;
	scanf("%lld %lld", &N, &K);

	long long x = N % K;
	if (x <= K / 2) printf("%lld\n", x);
	else printf("%lld\n", K - x);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 128
N, K = map(int, input().split())
Vs = list(map(int, input().split()))
max_v = 0
R = min(N, K)
for r in range(R+1):
  for a in range(r+1):
    b = r - a
    inh = sorted(Vs[:a] + Vs[N-b:])
    for d in range(min(r, K-r)+1):
      max_v = max(max_v, sum(inh[d:]))

print(max_v)


Measured memory_bytes: 3064
/*
無向グラフに対して使う

vector<int>を引数にすることを前提にしている
edgeなどを使う場合には、eの所をe.toにする必要がある
（逆に言えばそれだけでいい）

O(V+E)

verify:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A&lang=ja
参考:
https://ei1333.github.io/luzhiled/snippets/graph/lowlink.html
http://hos.ac/slides/20110504_graph.pdf
*/

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
template<class T,class U>constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;}
template<class T,class U>constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;}
typedef pair<int,int> pii;


template<typename T>
struct LowLink{
    const vector<vector<T>> &g;
    int sz;
    vector<int> ord,low;
    vector<bool> used;
    vector<int> articulation;
    vector<pii> bridge;
    int k;

    void dfs(int idx,int par){
        used[idx]=true;
        ord[idx]=k++;
        low[idx]=ord[idx];
        bool is_articulation=false;
        int cnt=0;
        for(auto &e:g[idx]){
            if(!used[e]){
                cnt++;
                dfs(e,idx);
                chmin(low[idx],low[e]);
                if(ord[idx]<low[e]) bridge.emplace_back(minmax(idx,e));
                is_articulation |=(par!=-1 && ord[idx]<=low[e]);
            }else if(e!=par){
                chmin(low[idx],ord[e]);
            }
        }
        is_articulation |= (par==-1 && cnt>=2);
        if(is_articulation) articulation.push_back(idx);

    }

    LowLink(const vector<vector<T>> &g):g(g){
        sz=g.size();
        used.assign(sz,false);
        ord.assign(sz,0);
        low.assign(sz,0);
        k=0;
        for(int i=0;i<sz;i++){
            if(!used[i]) dfs(i,-1);
        }
    }


};

signed main(){
    int v,e;
    cin>>v>>e;
    vector<vector<int>> g(v);
    for(int i=0;i<e;i++){
        int s,t;
        cin>>s>>t;
        g[s].push_back(t);
        g[t].push_back(s);
    }
    LowLink<int> l(g);
    vector<int> buri=l.articulation;
    sort(buri.begin(),buri.end());
    for(int i:buri){
        cout<<i<<endl;
    }
}


Measured memory_bytes: 4516
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ull, ull> UP;
typedef tuple<int, int, int> T;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int gcd(int a, int b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
int digisum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}

int s[100] = {};
int main() {
	ll ans = 0;
	int a, b;
	cin >> a >> b;
	FOR(i, a, b + 1) {
		string s = to_string(i);
		string t = s;
		reverse(t.begin(), t.end());
		if (s == t)ans++;
	}

	cout << ans << endl;
}



Measured memory_bytes: 256
def solve():
    N = int(input())
    s = ['' for _ in range(N)]
    t = [0] * N
    for i in range(N):
        si, ti = map(str, input().split())
        s[i], t[i] = si, int(ti)
    X = input()
    
    idx = s.index(X) + 1
    ans = sum(t[idx:])
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 3064
#include <stdio.h>
#include <string>
#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
#include <sstream>
#include <set>
#include <map>
#include <complex>
#include <deque>
#include <cstdio>
#include <cstdlib>

using namespace std;

#define inf 999999999
#define ll long long
#define sort(a,n) sort(a,a+n)
#define fi  first
#define se second
#define pb(a) push_back(a)

const ll MOD = 1000000007;
const double PI = 3.141592653589793238;

//--------------------------------------------------------------------------------------------//
int n;
int main() {
	cin >> n;
	int ans = 0;
	int i = 0;
	while (i<n) {
		ans++;
		i += ans;

	}
	cout << ans << endl;
}


Measured memory_bytes: 256
let n, a, b, c = Scanf.scanf " %d %s %s %s" @@ fun a b c d -> a, b, c, d
let ans = ref 0
let f i = if a.[i] = b.[i] && b.[i] = c.[i] then 0 else if a.[i] <> b.[i] && b.[i] <> c.[i] && c.[i] <> a.[i] then 2 else 1
let _ = for i = 0 to n - 1 do ans := !ans + f i done; Printf.printf "%d\n" !ans

Measured memory_bytes: 384
/*
最大公約数を再帰で求める　と思ったが　返り値も使わないし、
再帰でやる必要は特にないのでやらない
*/
 
#include <iostream>
 
using namespace std;
 
int main() {
    int x,y, next_x, next_y;
    
    cin >> x;
    cin >> y;
    
    //if 1 < y < x, then gcd(x, y) = gcd(y, x%y) 
    while(x%y!=0){
        next_x=y;
        next_y=x%y;
        
        x=next_x;
        y=next_y;
    }
    cout << y<< endl;
        return 0;
}

Measured memory_bytes: 1160