akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>

using namespace std;

long long N, A, B;

int main()
{
    scanf("%lld%lld%lld", &N, &A, &B);
    if (A == 0) printf("0\n");
    else if (B == 0) printf("%lld\n", N);
    else
    {
        long long sets = N / (A + B);
        printf("%lld\n", sets * A + min(N % (A + B), A));
    }
    return 0;
}


Measured memory_bytes: 128
tmp = gets.chomp.split(" ")
cnt = tmp[0].to_i
rem = tmp[1].to_i


donuts = Array.new
cnt.to_i.times do
  donuts.push(gets.chomp.to_i)
end

sm = donuts[0]
donuts.each do |donut|
  sm = donut if donut < sm
  rem -= donut
end

while rem >= sm do
  rem -= sm
  cnt += 1
end

puts cnt


Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <tuple>
#include <list>
#include <deque>
#include <stack>
#include <complex>
#include <functional>
#include <regex>
#include <map>
#include <numeric>

using namespace std;

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

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const int PI = acos(-1);
const int INF = numeric_limits<int>::infinity() / 2;
const ll INFLL = numeric_limits<ll>::infinity() / 2;

int dp[101][105501];
vector<int> p, c;

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int D, G; cin >> D >> G;

  G /= 100;

  p.resize(D+1);
  c.resize(D+1);

  rep(i, D) {
    cin >> p[i+1] >> c[i+1];
    c[i+1] /= 100;
  }

  REP(j, 1, G + 1) dp[0][j] = (1 << 30) / 2;
  dp[0][0] = 0;

  REP(i, 1, D + 1) REP(j, 1, G + 1) {
    dp[i][j] = dp[i-1][j];

    REP(k, 1, p[i]) {
      if (j - i * k >= 0) dp[i][j] = min(dp[i][j], dp[i-1][j-i*k] + k);
      else dp[i][j] = min(dp[i][j], k);
    }

    if (j - i * p[i] - c[i] >= 0) dp[i][j] = min(dp[i][j], dp[i-1][j-i*p[i]-c[i]] + p[i]);
    else dp[i][j] = min(dp[i][j], p[i]);
  }

  cout << dp[D][G] << endl;

  return 0;
}


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

using namespace std;

using ll=long long ;
void solve() {
    ll S;
    cin >> S;
    const ll N = 1000'000'000;
    ll x3 = (S%N)?N-S%N:0, y2 = 1;
    ll x2 = (S+x3)/N, y3 = N;
    cout << "0 0 " << x2 << ' '<<y2<<' '<<x3<<' '<<y3;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


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

int  main()
{
	int a,b; cin >> a >> b;

	if (a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0)
		cout << "Possible\n";
	else
		cout << "Impossible\n";
	return (0);
}


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

using namespace std;

int N;
pair<int, int> dp[100][50000];
vector<int> P;

pair<int, int> dfs(int idx, int ch) {
    if (idx == N) return make_pair(0, 0);
    if (dp[idx][ch].first >= 0) return dp[idx][ch];

    // 買わない
    dp[idx][ch] = dfs(idx + 1, ch);

    int p = P[idx] % 1000;

    if (p == 0) {
        if (ch >= 500) {
            // 小銭から500円玉を回収
            auto ret = dfs(idx + 1, ch - 500);
            ret.first += 1, ret.second -= P[idx];
            dp[idx][ch] = max(dp[idx][ch], ret);
        }
    } else if (p <= 500) {
        // 1000円投げて500円玉を回収
        auto ret = dfs(idx + 1, ch + 1000 - p - 500);
        ret.first += 1, ret.second -= P[idx];
        dp[idx][ch] = max(dp[idx][ch], ret);
    } else {
        // 1000円で小銭を回収
        auto ret = dfs(idx + 1, ch + 1000 - p);
        ret.second -= P[idx];
        dp[idx][ch] = max(dp[idx][ch], ret);

        int need = p - 500;
        if (need <= ch) {
            // 小銭を投げて500円玉を回収
            auto ret = dfs(idx + 1, ch - need);
            ret.first += 1;
            ret.second -= P[idx];
            dp[idx][ch] = max(dp[idx][ch], ret);
        }
    }
    return dp[idx][ch];
}

bool solve() {
    fill(dp[0], dp[100], make_pair(-1, -1));
    cin >> N;
    if (N == 0) return false;

    P.resize(N);
    for (auto& p : P) {
        cin >> p;
    }
    auto ans = dfs(0, 0);
    cout << ans.first << " " << -ans.second << endl;
    return true;
}

int main() {
    while (solve()) {}
    return 0;
}



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

int main() {
  int n,x;
  cin>>n>>x;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  long long count=1;
  long long d=0;
  for(int i=1;i<n+1;i++){
    long long tmp=d+a[i-1];
    d=tmp;
    if(d<=x){
      count++;
    }
    else break;
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define pii pair<ll,ll>
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

ll find(ll x, ll par[])
{
    if(x == par[x])
        return x;
    return par[x] = find(par[x], par);
}
 
void unio(ll x, ll y, ll par[], ll rank[], ll siz[])
{
    x = find(x,par);
    y = find(y,par);
    if(x == y)
        return;
    if(rank[x]>rank[y])
    {
        siz[x]+=siz[y];
        rank[x] = max(rank[x], rank[y] + 1);
        par[y] = x;
    }
    
    else
    {
        siz[y]+=siz[x];
        rank[y] = max(rank[y], rank[x] + 1);
        par[x] = y;
    }
}

int main()
{
  FAST/**/
   
   ll n;
   cin>>n;
   
   ll par[n], rank[n], siz[n];
   rep(n)
        par[i] = i, rank[i] = 0, siz[i] = 1;
   
   pair<pii,ll> arr[n];
   rep(n)
        cin>>arr[i].ff.ff>>arr[i].ff.ss, arr[i].ss = i;
   sort(arr,arr+n);
   set<pii> st;
   for(ll i=n-1;i>-1;i--)
   {
       auto it = st.lower_bound(mp(arr[i].ff.ss,i));
       ll maxy = arr[i].ff.ss;
       if(it!=st.end())
       {
           vector<pii> rem;
           
           while(it!=st.end())
           {
               rem.pb(*it);
               maxy = max(maxy, it->ff);
               unio(it->ss,arr[i].ss,par,rank,siz);
               it++;
           }
           
           autoit(rem,it1)
                st.erase(*it1);       
       }
       st.insert(mp(maxy,arr[i].ss)); 
   }
   
   st.clear();
   rep(n)
        arr[i].ff.ff*=(-1), arr[i].ff.ss*=(-1);
   sort(arr,arr+n);
   for(ll i=n-1;i>-1;i--)
   {
       auto it = st.lower_bound(mp(arr[i].ff.ss,i));
       ll maxy = arr[i].ff.ss;
       if(it!=st.end())
       {
           vector<pii> rem;
           
           while(it!=st.end())
           {
               rem.pb(*it);
               maxy = max(maxy, it->ff);
               unio(it->ss,arr[i].ss,par,rank,siz);
               it++;
           }
           
           autoit(rem,it1)
                st.erase(*it1);       
       }
       st.insert(mp(maxy,arr[i].ss)); 
   }
   
   rep(n)
        cout<<siz[find(i,par)]<<"\n";
        
   
   
   return 0;        
}  

  
          
   

Measured memory_bytes: 19196
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>

using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> vec(n,1);
    vector<bool> bl(n);
    bl[0]=1;
    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;
        x--;y--;
        vec[x]--;
        vec[y]++;
        if(bl[x]==1){
            bl[y]=1;
        }
        if(vec[x]==0){
            bl[x]=0;
        }
    }
    int c=0;
    for(int i=0;i<n;i++){
        if(bl[i]==1&&vec[i]>0){
            c++;
        }
    }
    cout<<c<<endl;
}

Measured memory_bytes: 640
N = int(input())
A = [0]+list(map(int,input().split()))+[0]

d_sum=0
for i in range(0, N+1):
    d_sum+=abs(A[i]-A[i+1])

for i in range(1, N+1):
    print(d_sum-abs(A[i]-A[i-1])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]))


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

using namespace std;
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for(int &x : a){
        scanf("%d", &x);
    }
    vector<bool> dp(k + 1);
    
    for(int i = 0; i<=k; i++){
        for(int x : a){
            if(i >= x && !dp[i - x]){
                dp[i] = true;
            }
        }
    }
    
    
    puts(dp[k] ? "First" : "Second");
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 1e5+17;
int a[MAXN];
int main(int argc ,char const *argv[])
{
    #ifdef noob
    freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
    #endif
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
    	cin>>a[i];
    }
    int inc = 0,dec = 0,mx=-1,mn = 1e9+1,ans=0;
    for (int i = 0; i < n; ++i)
    {
    	if(inc&&mx<=a[i])
    	{
    		if(dec&&a[i]>mx) dec=0;
    		mx = a[i];
    	}
    	else if(dec&&mn>=a[i])
    	{
    		if(inc&&a[i]<mx) inc=0;
    		mn = a[i];
    	}
    	else 
    	{
    		inc = dec = 1;
    		mx = mn = a[i];
    		ans++;
    	}
    	// debug(i);
    	// debug(inc);
    	// debug(dec);
    	// debug(ans);

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

Measured memory_bytes: 640
import java.util.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=sc.nextInt();
        int n=0;
        for(int i=a;i<=b;i++){
            if(c%i==0){
                n++;
            }
        }
        System.out.println(n);
    }
}



Measured memory_bytes: 26260
(n, m) = [int(i) for i in input().split()]
A = []
b = []
for i in range(n):
    A.append([int(j) for j in input().split()])

for i in range(m):
    b.append(int(input()))

c =[]
for i in range(n):
    s = 0
    for j in range(m):
        s += A[i][j] * b[j]
    print(s)

Measured memory_bytes: 7016
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
      	int M = sc.nextInt();
        int N = sc.nextInt();
		if (N % M == 0)System.out.println(N + M);
        else System.out.println(N - M) ;
	}
}


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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<< "\n"


int main(){
    int a,b;
    cin >> a >> b;
    int d = a/b;
    int r = a%b;
    double f = a*1.0/b;
    printf("%d %d %f\n",d,r,f);
    return 0;
}



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

void var(int n) {
  vector<int> score(n);
  double mean = 0;
  for (int i = 0; i < n; i++) {
    cin >> score.at(i);
    mean += score.at(i);
  }
  mean /= n;
  double variance = 0;
  for (int i = 0; i < n; i++) {
    variance += (score.at(i) - mean) * (score.at(i) - mean);
  }
  variance /= n;
  cout << fixed << setprecision(8) << sqrt(variance) << endl;
}

int main() {
  int n;
  while (cin >> n) {
    if (n == 0) break;
    var(n);
  }
}


Measured memory_bytes: 3248
S = raw_input()

count = 0
idx = 0
a_count = 0
while idx < len(S):
    if a_count > 0:
        if S[idx: idx+2] == 'BC':
            count += a_count
            idx += 2
            continue
    if S[idx] == 'A':
        a_count += 1
    else:
        a_count = 0
    idx += 1

print count


Measured memory_bytes: 2948
#include<bits/stdc++.h>
#define ll long long int
#define db long double
#define ull unsigned long long int
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
#define Nmax 1000005
#define INF 1000000000
#define MOD 1000000007
#define MAXN 1000005
 
using namespace std;

ll n;

vector<vector<ll>> matrix_mul(vector<vector<ll>>&v1,vector<vector<ll>>&v2)
{
	vector<vector<ll>>res(n,vector<ll>(n,0));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int k=0;k<n;k++)
			{
				res[i][k]+=v1[i][j]*v2[j][k];
				res[i][k]%=MOD;
			}
		}
	}
	return res;
}

vector<vector<ll>> matrix_expo(vector<vector<ll>>&base,ll exponent)
{
	vector<vector<ll>>res(n,vector<ll>(n,0));
	for(int  i=0;i<n;i++) res[i][i]=1;
	while(exponent)
	{
		if(exponent%2==1)
		{
			res=matrix_mul(res,base);
		}
		base=matrix_mul(base,base);
		exponent/=2;
	}
	return res;
}

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    int tests=1;
    // cin>>tests;
    while(tests--)
    {
    	ll i,j,k;
    	cin>>n>>k;
    	vector<vector<ll>>base(n,vector<ll>(n)),ans;
    	rep(i,0,n-1)
    	{
    		rep(j,0,n-1)
    		cin>>base[i][j];
    	}

    	ans=matrix_expo(base,k);
    	ll tot=0;
    	rep(i,0,n-1)
    	{
    		rep(j,0,n-1)
    		{
    			tot+=ans[i][j];
    			tot%=MOD;
    		}
    	}
    	cout<<tot;

    }
    	return 0;
    
}

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

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
template <class T>
T GCD(T a, T b)
{
    T r;
    while (a)
        r = b, b = a, a = r % a;
    return b;
}
template <class T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repe(i, n) for (ll i = 0; i <= (n); i++)
#define repd(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<ll> vl;
#define ERASE(x) x.erase(unique(ALL(x)), x.end()); // erase same elements
#define VEC(type, c, n)     \
    std::vector<type> c(n); \
    for (auto &i : c)       \
        std::cin >> i;

// input
#define INIT                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);
#define VAR(type, ...) \
    type __VA_ARGS__;  \
    MACRO_VAR_Scan(__VA_ARGS__);
template <typename T>
void MACRO_VAR_Scan(T &t)
{
    std::cin >> t;
}
template <typename First, typename... Rest>
void MACRO_VAR_Scan(First &first, Rest &... rest)
{
    std::cin >> first;
    MACRO_VAR_Scan(rest...);
}

// output
template <typename T>
void MACRO_OUT(const T t) { std::cout << t; }

#define OUT(...) MACRO_OUT(__VA_ARGS__);
#define SP std::cout << " ";
#define TAB std::cout << "\t";
#define BR std::cout << "\n";
#define ENDL std::cout << std::endl;

#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define yes() printf("yes\n")
#define no() printf("no\n")
#define ln cout << '\n'
template <Z A>
void pr(A a)
{
    cout << a;
    ln;
}
template <Z A, Z B>
void pr(A a, B b)
{
    cout << a << ' ';
}

ll ans = 0;
bool check = 0;
bool boo = 0;
string s, t;
int N = 3;
vector<int> v(N);
int a, b, c, d, n, m = 0;
int x = 0, y = 0;
int sum;
char ch;

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// cout << (conditon ? (result:  == 1 ): (==0)) << endl; <- output result of if
// long long 型が表せる値の上限はおよそ 9 × 10＾18 です．
int main()
{
    INIT;
    cin >> s;
    rep(i, s.length())
    {
        if (s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C')
        {
            x++;
            m = max(m, x);
        }
        else
            x = 0;
    }

    pr(m);

    return 0;
}


Measured memory_bytes: 3608
#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<cstdio>
#include<functional>
#include<cstdlib>

#define _A_ true

using namespace std;

typedef pair<int,string> P;

int main(){
  int n;
  //map<string,int> dic;
  P dic[10000];
  string s[10000];
  int index=0;
  string si;
  char han;
  map<string,int> Map;
  map<string,bool> used;

  /*
  P p[3];
  p[0] = P(2,"ba");
  p[1] = P(2,"a");
  p[2] = P(1,"c");
  sort(p,p+3);
  for(int i=0;i<3;i++){
    cout << p[i].first << " " << p[i].second << endl;
  }
  */

  while(_A_){
    cin >> n;
    if(n == 0)break;
    index = 0;
    int Nc=0;
    for(int i=0;i<10000;i++){
      dic[i].first = -1;
    }
    Map.clear();
    used.clear();
    int temp = 0,word_sum = 0;
    char c;
    for(int i=0;i<10000;i++)s[i].clear();
    while(temp < n){
      cin >> s[word_sum++];
      scanf("%c",&c);
      if(c == '\n')temp++;
      //cout << "c = " << c;
      //cout << "temp =" << temp << endl;
    }
    cin >> han; 

    

    for(int i = 0;i < word_sum;i++){
      if(s[i][0] == han){
	Map[s[i]]++;
      }
    }  

    int index2=0;

    for(int i=0;i< word_sum;i++){
      if(s[i][0] == han && !used[s[i]]){
	dic[index2] = P(Map[s[i]],s[i]);
	index2++;
	Nc++;
	used[s[i]]=true;
      }
    }
    
    sort(dic,dic+index2,greater<P>());
    
    int index3=0;
    int flag = dic[0].first;
    int ccounter=0;
    map<int,string> Nari;
    int point=0;    
    set<string> Answer;
    int Count=0;

    //for(int i=0;i<index2;i++){
    //cout << dic[i].first << " " <<  dic[i].second << endl;
    //}
    //cout << "------------" << endl;


    if(index2 == 0){
      cout << "NA";
    }else{
      for(int i = 0;i <= index2;i++){
	if(flag != dic[i].first ){
	  //cout << "flag = " << flag  << " " << point <<" "<< i << endl;
	  for(int j=point;j<i;j++){
	    Answer.insert(dic[j].second);
	  }	  
	  if(point == i){
	    Answer.insert(dic[point].second);
	  }
	  set<string>::iterator it = Answer.begin();
	  while(it != Answer.end()){
	    cout << *it;
	    it++;
	    Count++;
	    if(Count < 5&& Nc != Count ){
	      cout << " ";
	    }else{break;}
	  }
	  Answer.clear();
	  point = i;
	  flag = dic[i].first;
	}
      }
    
  
    }
    cout << endl;
 
  }
  return 0;
}

Measured memory_bytes: 1112
nums = ["0111111", "0000110", "1011011", "1001111", "1100110",
        "1101101", "1111101", "0100111", "1111111", "1101111"]

while 1:
    n = int(input())
    if n == -1:
        break

    sig = "0000000"
    for _ in range(n):
        d = int(input())
        num = nums[d]
        out = ""
        for s, n in zip(sig, num):
            if s == n:
                out += "0"
            else:
                out += "1"

        print(out)
        sig = num



Measured memory_bytes: 5596
N=int(input())
A=list(map(int,input().split()))
x=[]
for i in range(N):
    x.append(A[i]-(i+1))
x.sort()
cnt=0
#print(x)
line=x[N//2]
for i in range(N):
    cnt=cnt+abs(line-x[i])
print(cnt)

Measured memory_bytes: 99796
/*
    Created by Tejas Chaudhari
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef double lf;
typedef bool bl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<lf> vd;
typedef vector<bl> vb;
typedef string st;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

#define INF (LONG_LONG_MAX / 4)
#define Mod % 1000000007
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

void re_curse() {
    ll k;
    cin>>k;
    ll c = 7 % k;
    ll ans = 1;
    vb found(k, false);
    while (c) {
        if (found[c]) {
            cout<<-1<<endl;
            return ;
        }
        found[c] = true;
        c = (c*10 + 7) % k;
        ++ans;
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin>>t;
    for (int i = 1; i <= t; ++i) {
        re_curse();
    }
    return 0;
}


Measured memory_bytes: 3728
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

vector<int> init(int size){
  vector<int> par(size,-1);
  return par;
}

int root(int x, vector<int>& par){
  if(par[x] < 0){
    return x;
  }else{
    return par[x] = root(par[x],par);
  }
}

bool same(int x, int y, vector<int>& par){
  return root(x, par) == root(y, par);
}

void unite(int x, int y, vector<int>& par){
  x = root(x, par), y = root(y, par);
  if(same(x,y, par))return;
  par[x] += par[y];
  par[y] = x;
}

int size(int x, vector<int>& par){
  return -par[root(x, par)];
}

int pow(int x, int n){
  if(n == 0)return 1;
  if(n % 2 == 0)return pow(x * x % MOD, n/2);
  else return x * pow(x, n-1) % MOD;
}


signed main(){
  int n,k;cin>>n>>k;
  vector<double> v(n);
  repd(i,1,n+1){
    int p = i, ret = 1;
    while(p < k){
      p *= 2;ret *= 2;
    }
    v[i-1] = ret;
  }
  int ansi = 1;
  repd(i,1,n)ansi += v[0]/v[i];
  long double b = v[0]*n, c = ansi;

  std::cout << std::setprecision(10);
  std::cout << c/b << endl;; // "3.1"
}


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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

constexpr ll TEN(int n)
{
    return (n == 0) ? 1 : 10 * TEN(n - 1);
}

template <class T, class U>
void chmin(T &t, const U &u)
{
    if (t > u)
        t = u;
}
template <class T, class U>
void chmax(T &t, const U &u)
{
    if (t < u)
        t = u;
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "{";
    rep(i, v.size())
    {
        if (i)
            os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out()
{
    cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

constexpr ll INF = TEN(18);

int main()
{
    int N, K;
    cin >> N >> K;
    V<int> P(N), C(N);
    rep(i, N) cin >> P[i], --P[i];
    rep(i, N) cin >> C[i];

    ll ans = -INF;

    rep(i, N)
    {
        int v = i;
        ll cycle_sum = 0;
        int cycle_cnt = 0;

        while (true)
        {
            cycle_cnt++;
            cycle_sum += C[v];
            v = P[v];
            if (v == i)
                break;
        }

        ll path = 0;
        int cnt = 0;

        while (true)
        {
            cnt++;
            path += C[v];

            if (cnt > K)
                break;

            int num = (K - cnt) / cycle_cnt;
            ll score = path + max(0ll, cycle_sum) * num;
            chmax(ans, score);

            v = P[v];
            if (v == i)
                break;
        }
    }

    cout << ans << endl;

    return 0;
}


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

int main(){
  int N,M,sum=0;
  cin>>N>>M;
  vector<int> A(M);
  for(int i=0; i<M; i++){
    cin>>A.at(i);
    sum+=A.at(i);
  }
  cout<<(N-sum>=0?N-sum:-1)<<endl;
}
  

Measured memory_bytes: 3676
def binarySearch (ary, n, key)

  left  = 0
  right = n
  mid   = n / 2

  while left < right

    if ary[mid] == key then return 1

    elsif key < ary[mid] then right = mid

    else left = mid + 1 end

    mid = (left + right) / 2

  end

  return 0
end

num_of_ary = gets.to_i
ary        = gets.split.map &:to_i
num_of_key = gets
keys       = gets.split.map &:to_i

answer = 0

keys.each { |key| answer += binarySearch(ary, num_of_ary, key) }

puts answer



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

using namespace std;

#define int long long
#define pb push_back
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0);

/*
 * void init(int n) // n個で初期化
 * int find(int x) // 木の中のxの深さを返す
 * void unite(int x, int y) // xとyを統合
 * bool same(int x, int y) { // xとyが等しいかどうか判定する
 */

class UF {

  vector<int> par; // 親
  vector<int> rank; // 深さ

public:

  void init(int n) { // n個で初期化
    for(int i=0;i<n;i++) {
      par.push_back(i);
      rank.push_back(0);
    }
  }

  int find(int x) { // 木の中のxの深さを返す
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
  }

  void unite(int x, int y) { // xとyを統合する
    x = find(x);
    y = find(y);
    if (x == y) return;

    if(rank[x] < rank[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if (rank[x] == rank[y]) rank[x]++;
    }
  }

  bool same(int x, int y) { // xとyが等しいかどうか判定する
    return find(x) == find(y);
  }
};

vector<pair<int, int>> p;

bool link(int k, int n, int m) {
  UF u;
  u.init(n+1);
  REP(i, m) {
    if(i != k) {
      u.unite(p[i].first, p[i].second);
    }
  }
  FOR(i, 1, n) {
    //cout << k << ":" << i << ":" << u.same(i, i+1) << endl;
    if(!u.same(i, i+1)) return false;
  }

  return true;
}


signed main () {
  cin.tie(0);
  cout << setprecision(10);

  int n,m;cin>>n>>m;
  p.resize(m);
  REP(i, m) {
    cin >> p[i].first >> p[i].second;
  }

  int ans = 0;
  REP(i, m) {
    bool a = link(i, n, m);
    if(!a) ans++;
  }
  
  cout << ans << endl;
  
}


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

using namespace std;

int main() {
    unsigned int n;
    cin >> n;

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

    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
        if ((vt[i] - vt[i - 1]) * (vt[i] - vt[i + 1]) < 0) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    ll a[100002];
    for(int i = 0; i < n; i++) cin >> a[i];
    ll ans = a[0] - 1;
    ll r = 1;
    for(int i = 1; i < n; i++){
        ans += (a[i] - 1) / (r + 1);
        if(a[i] == r + 1) r++;
    }
    cout << ans << endl;
}

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

int main()
{
  int N; cin >> N;
  ll A[N]; rep(i,N) cin >> A[i];
  int ans = 0;
  
  sort(A, A+N);

  int i = 0;
  while(i < N)
  {
    int check = A[i];
    int count = 0;
    while(A[i] == check && i < N)
    {
      count++;
      i++;
    }
    ans += count % 2;
  }
  cout << ans << endl;
}

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

using namespace std;

int main() {
  int c11, c12, c13;
  int c21, c22, c23;
  int c31, c32, c33;

  cin >> c11 >> c12 >> c13;
  cin >> c21 >> c22 >> c23;
  cin >> c31 >> c32 >> c33;

  string answer = "No";

  for (int i = 0; i <= 100; i++) {
    int a1 = i;
    int b1 = c11 - a1;

    int a2 = c21 - b1;
    int a3 = c31 - b1;
    int b2 = c12 - a1;
    int b3 = c13 - a1;

    if (c22 == a2 + b2 && c23 == a2 + b3 && c32 == a3 + b2 && c33 == a3 + b3) {
      answer = "Yes";
      break;
    }
  }

  cout << answer << endl;
}


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

mod = 10**9 +7
N = int(input())
X = list(map(int, input().split()))

factorial=[1]
for i in range(1,N):
    factorial.append(factorial[-1] *i %mod)

ans=0
for i in range(1,N):
    ans = (ans*i + (X[-1]-X[i-1])*factorial[i-1]) %mod

print(ans)

Measured memory_bytes: 14252
a, b, c, d = [int(v) for v in list(input())]

for op1 in ['+', '-']:
    for op2 in ['+', '-']:
        for op3 in ['+', '-']:
            tmp = a
            if op1 == '+':
                tmp += b
            else:
                tmp -= b

            if op2 == '+':
                tmp += c
            else:
                tmp -= c

            if op3 == '+':
                tmp += d
            else:
                tmp -= d

            if tmp == 7:
                ans = '{0}{1}{2}{3}{4}{5}{6}=7'.format(a, op1, b, op2, c, op3, d)

print(ans)

Measured memory_bytes: 3064
while True:
  n = int(input())
  if n==0:
    break

  grid = [[0 for i in range(21)] for i in range(21)]
  for i in range(n):
    x, y = list(map(int, input().split()))
    grid[x][y] = 1

  x, y = 10, 10
  grid[x][y] = 0
  m = int(input())
  for i in range(m):
    d, l = input().split()
    l = int(l)
    nx, ny = x, y
    if d=="N":
      ny += l
      for j in range(y, ny+1):
        grid[x][j] = 0
    elif d=="S":
      ny -= l
      for j in range(y, ny-1, -1):
        grid[x][j] = 0
    elif d=="E":
      nx += l
      for j in range(x, nx+1):
        grid[j][y] = 0
    else:
      nx -= l
      for j in range(x, nx-1, -1):
        grid[j][y] = 0
    x, y = nx, ny

  flag = True
  for i in range(21):
    for j in range(21):
      if grid[i][j] == 1:
        flag = False
  if flag:
    print("Yes")
  else:
    print("No")


Measured memory_bytes: 5632
from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(list(input()))

def bfs(initial):
    distance = [[-1] * w for _ in range(h)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x,y = current_node
        for i,j in ((1,0),(-1,0),(0,1),(0,-1)):
            new_x, new_y = x+i, y+j
            if 0<=new_x<h and 0<=new_y<w:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y]==-1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]

ans = 0
for i in range(h):
    for j in range(w):
        if (maze[i][j] == "#"):
            continue
        solution = bfs((i,j))
        ans = max(ans,solution)

print(ans)

Measured memory_bytes: 44524
s = gets.chomp.chars
if s[0] == "A"
  count = 0
  s[2..-2].map do |i|
    if i == "C"
      s.delete(i)
      count += 1
    end
  end
  s.delete(s[0])
end
puts count != 1 || s.join.match(/[A-Z]/) ? "WA" : "AC"



Measured memory_bytes: 1788
import java.util.Scanner;

public class Main {
     public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int f1, f2;
		double f3;
		f1 = x / y;
		f2 = x % y;
		f3 = (double)x/(double)y;
		System.out.printf("%d %d %.5f\n", f1, f2, f3);	
     }
}



Measured memory_bytes: 26560
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;

ll gcdd(ll a, ll b) {
  while (true) {
    if (a > b) {
      swap(a, b);
    }
    b = b % a;
    if (b == 0) {
      return a;
    }
  }
}

int main() {
  int N, M;
  cin >> N >> M;
  VI a(N);
  rep(i, N) { cin >> a.at(i); }
  int x = a.at(0);
  int cnt = 0;
  while (x % 2 == 0) {
    cnt += 1;
    x /= 2;
  }
  int twopow = 1 << cnt;
  int twopow2 = twopow * 2;
  ll odd = 1;
  int oddmax = (M - 1) / (twopow / 2) + 1;
  rep(i, N) {
    if (a.at(i) % twopow == 0 && a.at(i) % twopow2 != 0) {
      a.at(i) /= twopow;
      ll gc = gcdd(odd, (ll)a.at(i));
      odd *= a.at(i) / gc;
      if (odd > oddmax) {
        cout << 0 << endl;
        return 0;
      }
    } else {
      cout << 0 << endl;
      return 0;
    }
  }
  int q = M / (odd * (twopow / 2));
  cout << (q + 1) / 2 << endl;

  return 0;
}


Measured memory_bytes: 768
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

x = sum(B) - sum(A)
if x >= 0 and sum([max(a-b, a+b&1) for a, b in zip(A, B)]) <= x:
    print("Yes")
else:
    print("No")

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

int N,M; // Nけん回ってM本買えるか。
vector<pair<ll,ll> > drink;


int main()
{
	cin >> N >> M;
	drink.resize(N);
	for(int i=0;i<N;++i){
		ll a,b;
		cin >> a >> b;
		drink.push_back(make_pair(a,b));
	}
	sort(drink.begin(),drink.end());

	int count = 0;
	ll ans = 0;
	while(M > 0){
		ll cost = drink[count].first;
		ll capa = drink[count].second;
		if(capa > M){
			ans += M * cost;
			break;
		} else {
			ans += capa * cost;
			M -= capa;
		}
		count++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4864
n, m = [int(i) for i in input().split()]

matrix = []
for ni in range(n):
    matrix.append([int(a) for a in input().split()])

vector = []
for mi in range(m):
    vector.append(int(input()))

b = []
for ni in range(n):
    sum = 0
    for mi in range(m):
        sum += matrix[ni][mi] * vector[mi]

    print(sum)

Measured memory_bytes: 8044
N=int(input())

flag=0
for i in range(int(N^(1//2))+1):
    if N*2==i*(i+1):
        flag=1
        d=i
        break
if flag==0:
    print('No')
    exit(0)

ls=[[0 for _ in range(d)] for _ in range(d+1)]
for i in range(d):
    ls[0][i]=i+1

for j in range(1,d+1):
    for i in range(j):
        ls[j][i]=ls[j-i-1][j-1]
    for i in range(d-j):
        ls[j][i+j]=i+max(ls[j-1])+1
print('Yes')
print(d+1)
for i in range(len(ls)):
    print(d, end=' ')
    for j in ls[i]:
        print(j, end=' ')
    print()


Measured memory_bytes: 9296
#include<bits/stdc++.h>
using namespace std;
#define OUT(x) cout<<x<<endl
struct box{
  int x,y;
};
int ix[] = {-1,0,1,0};
int iy[] = {0,1,0,-1};
int main(){
  int n,b,h,maxx,maxy,minx,miny,ansx,ansy;
  while(cin >> n&&n){
    maxx=maxy=minx=miny=0;
    box bbox[201];
    bbox[0].x = bbox[0].y = 0;
    for(int i=1;i<n;i++){
      cin >> b >> h;
      bbox[i].x = bbox[b].x + ix[h];
      bbox[i].y = bbox[b].y + iy[h];
      if(bbox[i].x > maxx)maxx = bbox[i].x;
      else if(bbox[i].x < minx)minx = bbox[i].x;
      if(bbox[i].y > maxy)maxy = bbox[i].y;
      else if(bbox[i].y < miny)miny = bbox[i].y;
    }
    ansx = maxx - minx + 1;
    ansy = maxy - miny + 1;
    cout << ansx << " " << ansy << endl;
  }
}

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

using pii = pair <int, int>;

#define N 300000

int n, m;
int dp[N], val[N], w[N];

int D, Q;

vector <pii> can[1030];

void query(int &ans, int v, int L, int cur) {
	if (v <= m) {
		ans = max(ans, cur + (--lower_bound(can[v].begin(), can[v].end(), pii(L + 1, 0))) -> second);
		return;
	}
	query(ans, v >> 1, L, cur);
	if (L >= w[v]) query(ans, v >> 1, L - w[v], cur + val[v]);
	return;
}

int main() {
	D = 10;
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) scanf("%d %d", &val[i], &w[i]);
	dp[1] = 0;
	for (int i = 2; i <= n; i ++) dp[i] = dp[i>>1] + 1;
	m = min(n, (1<<D) - 1);
	can[0] = {{0, 0}};
	for (int i = 1; i <= m; i ++) {
		auto &res = can[i];
		auto &from = can[i>>1];
		vector <pii> tmp;
		tmp = from;
		for (auto x : from) {
			tmp.emplace_back(x.first + w[i], x.second + val[i]);
		}
		sort(tmp.begin(), tmp.end());
		for (auto x : tmp) {
			if (!res.empty() && res.back().second >= x.second) continue;
			res.push_back(x);
		}
	}
	scanf("%d", &Q);
	while (Q --) {
		int v, L, ans = 0;
		scanf("%d %d", &v, &L);
		query(ans, v, L, 0);
		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 12276
def calculate_sum_of_digits(n):
    result = 0
    while n != 0:
        result += (n % 10)
        n //= 10

    return result


n = int(input())
sum_of_digits = calculate_sum_of_digits(n)
result = False
if n % sum_of_digits == 0:
    result = True

print("Yes" if result else "No")


Measured memory_bytes: 3064
def f(x):
    return x * (x + 1) // 2


if __name__ == "__main__":
    N = int(input())
    for i in range(0, N + 1):
        if f(i) >= N:
            x, sum_ = i, f(i)
            break

    r = sum_ - N
    for i in range(1, x + 1):
        if i != r:
            print(i)


Measured memory_bytes: 74264
#include<stdio.h>
int main()
{
    int t,h,m,s,rem;
    scanf("%d",&t);
    h=t/3600;
    rem=t%3600;
    m=rem/60;
    rem=t%60;
    s=rem;
    printf("%d:%d:%d\n",h,m,s);
}



Measured memory_bytes: 2044
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll n;
    cin >> n;
    for(ll i = 1; i <= 3500; i++) for(ll j = 1; j <= 3500; j++){
        if(4 * i * j - n * (i + j) <= 0) continue;
        ll k = (n * i * j) / (4 * i * j - n * (i + j));
        if(4 * i * j * k == n * (i * j + j * k + k * i)){
            cout << i << " " << j << " " << k << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def kaizyo(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n=0,d=0) Array.new(n,d)end
def na2(n=0,m=0,d=0) Array.new(n){Array.new(m,d)}end
def na3(n=0,m=0,l=0,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
h,w,k=inp
d=[]
x=y=0
h.times do |i|
  dd=inps[0]
  if(dd.include?("S"))
    y=i
    x=dd.index("S")
  end
  d[i] = dd
end
que = [[y,x,k]]
min = 9999999
memo = na2(h+100,w+100)
if(x <= 0 or y <= 0 or x >= w-1 or y>=h-1)
  puts 0
  exit
end
while(que.size > 0)
  dd = que.shift
  x,y = dd[1],dd[0]
  if(x < 0 or y < 0 or x >= w or y>=h)
    puts 1
    exit
  end
  next if(memo[y][x] == 1)
  next if(d[y][x] == "#")
  if(x <= 0 or y <= 0 or x >= w-1 or y>=h-1)
    puts 1
    exit
  end
  min = [x,y,h-y-1,w-x-1,min].min
  next if(dd[2] == 0)
  que.push([y-1,x,dd[2]-1])
  que.push([y+1,x,dd[2]-1])
  que.push([y,x+1,dd[2]-1])
  que.push([y,x-1,dd[2]-1])
  memo[y][x] = 1
end
min = [1,min].max
puts 2+(min-1)/k 
=begin
=end

Measured memory_bytes: 11388
#include<cstdio>
#include<cstring> 
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=5e5+5;
char a[10];
int n;
int main(){
	scanf("%s",a+1);
	if(a[3]==a[4]&&a[5]==a[6]){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <math.h>
#include <complex>
#include <cassert>
#define rep(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
typedef long long int ll;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const ll INF = 4e18;



int main(){
	int n; cin>>n;
	vector<ll> a(n);
	ll ans=0;
	rep(i,0,n){
		int x,y; cin>>x>>y;
		ans-=y;
		a[i]=x+y;
	}
	sort(a.begin(),a.end(),greater<ll>());
	rep(i,0,n)if(i%2==0)ans+=a[i];
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
using ll =long long;
int main() {
	int A,B,C;
	int tmp;
	cin >> A>>B>>C;
	tmp = A;
	A = B;
	B = tmp;
	tmp = A;
	A = C;
	C = tmp;
	cout <<A <<endl<<B<<endl <<C;
	

}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int MAX = 100100;
int n,m,q;
int f[MAX];
int find(int a){
  return f[a] == a ? a : f[a] = find(f[a]);
}
int ss = 1;
void uni(int a,int b){
  a = find(a);
  b = find(b);
  if(a == b)return;
  f[a] = b;
  ss--;
}
void nope(){
  cout << "No\n";
  exit(0);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> m >> q;
  R(i,n){
    f[i] = i;
  }
  ss = n;
  vector<PII> x;
  R(i,q){
    int a,b,c;
    cin >> a >> b >> c;
    if(c){
      x.PB({a,b});
    }else{
      uni(a,b);
    }
  }
  if(SZ(x) && (ss <= 2 || m == n-1 ))nope();
  for(PII el:x){
    if(find(el.FI) == find(el.SE))nope();
  }
  if(n-1 + (ss-1) * (ss-2) / 2 < m)nope();
  cout << "Yes\n";
}


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

int main(){
  int n, k;
  cin >> n >> k;

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

  int dist = 0;

  for(int i=0; i<n; i++){
    if(xs[i] < abs(k - xs[i]))
      dist += xs[i]*2;
    else
      dist += abs(k-xs[i])*2;
  }

  cout << dist << endl;
  
  return 0;
}


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

int main(int argc, char *argv[]) {
  int n, q;
  std::cin >> n;
  long long a[1001];
  for (int i = 0; i < n; ++i)
    std::cin >> a[i];

  std::cin >> q;
  for (int i = 0; i < q; ++i) {
    int b, m, e;
    std::cin >> b >> m >> e;
    std::rotate(a + b, a + m, a + e);
  }

  for (int i = 0; i < n; ++i) {
    if (i > 0)
      std::cout << " ";
    std::cout << a[i];
  }
  std::cout << std::endl;
}



Measured memory_bytes: 3172
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
using namespace std;
int main()
{
	int a,b; 
    cin>>a>>b;
    if(a>0)cout<<"Positive\n";
    else if(b>=0)cout<<"Zero\n";
    else if((abs(b)-abs(a)+1)%2==0)cout<<"Positive\n";
    else cout<<"Negative\n";
    return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w,a,b;
    cin >> h >> w >> a >> b;
    REP(i,h){
        bool hb = (i<b);
        REP(j,w){
            bool wb = (j<a);
            int ans;
            if((hb&&wb)||((!hb)&&(!wb))){
                ans = 1;
            }else{
                ans = 0;
            }
            cout << ans << ((j==w-1)?("\n"):(""));
        }
    }
    return 0;
}

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

#define cc(x) cout << (x) << endl
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); ++i)
typedef long long ll;

template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

const ll inf = 1LL<<58;
const int iinf = 1<<30;

ll gcd(ll a, ll b){
    if(b==0){
        return a;
    }
    return gcd(b, a%b);
}

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n){
        cin >> a[i];
    }
    ll tmp=gcd(a[0], a[1]);
    rep(i,n-2){
        tmp=gcd(tmp,a[i+2]);
    }
    cc(tmp);
}

Measured memory_bytes: 1024
N, W = (int(n) for n in input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = (int(n) for n in input().split())
    w.append(w_)
    v.append(v_)

def knapsack_dp(W, w, v):
    """Solve knapsack problem by dynamic programming"""
    N = len(w)
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(N):
        for w_ in range(W + 1):
            if w_ >= w[i]:
                dp[i + 1][w_] = max(dp[i][w_], dp[i][w_ - w[i]] + v[i])
            else:
                dp[i + 1][w_] = dp[i][w_]

    return dp[N][W]

print(knapsack_dp(W, w, v))

Measured memory_bytes: 118512
#include<iostream>
#include<string>

using namespace std;

int main() {
	string s,w="W";
	int n, i, ce = 0, cw = 0, min, sum;

	cin >> n;
	cin >> s;
	
	int* sw = new int [n];
	int* se = new int [n];
	min = n;

	for (i = 0; i < n; i++) {
		if (s[i] == w[0])
			sw[i] = ++cw;
		else
			sw[i] = cw;
	}
	for (i = n - 1; i >= 0; i--) {
		if (s[i] != w[0])
			se[i] = ++ce;
		else
			se[i] = ce;
	}
	
	min = se[0];
	sum = sw[n - 1];
	if (min > sum)
		min = sum;

	for(i = 1; i < n-1; i++) {
		sum = sw[i - 1] + se[i + 1];
		if (min > sum)
			min = sum;
	}
	cout << min;

	return 0;
}

Measured memory_bytes: 2948
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

  ll n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  ll rec[n] = {};
  REP(i, n - 1){
    if(s[i] == 'A' && s[i + 1] == 'C'){
      rec[i + 1] = rec[i] + 1;
    }
    else rec[i + 1] = rec[i];
  }
  ll l, r, ans;
  REP(i, q){
    ans = 0;
    cin >> l >> r;
    l--;
    r--;
    ans = rec[r] - rec[l];
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 1872
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int f[N][N],sum[N][N];
int n,mod,k;
int C[N][N];
void init()
{
	for(int i=0;i<N;i++)
		C[i][0]=C[i][i]=1;
	for(int i=1;i<N;i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
int main()
{
	scanf("%d%d%d",&n,&k,&mod);
	init();
	for(int i=0;i<=k;i++)
		f[1][i]=1;
	for(int j=k;j>=0;j--)
		sum[1][j]=(sum[1][j+1]+f[1][j])%mod;
	for(int i=2;i<=n+1;i++)
		for(int j=k;j>=0;j--)
		{
			for(int sz=1;sz<i;sz++)
				f[i][j]=(f[i][j]+1ll*f[i-sz][j]*sum[sz][j+1]%mod*C[i-2][sz-1])%mod;
			sum[i][j]=(sum[i][j+1]+f[i][j])%mod;
		}
	printf("%d\n",f[n+1][0]);
	return 0;
}


Measured memory_bytes: 2432