akhauriyash/Code-Regression huggingface dataset:
object Main extends App {
  val sc = new FastScanner(System.in)
  val n = sc.nextInt()
  val a, b = Array.fill(n)(sc.nextInt())

  var ans = 0L
  for (i <- 0 to 28) {
    val t = 1 << i
    val mask = (1 << (i + 1)) - 1
    val am = a.map(_ & mask)
    val bm = b.map(_ & mask).sorted

    def lowerBound(a: Array[Int], k: Int): Int = {
      def lowerBound(begin: Int, end: Int): Int = {
        if (end - begin <= 1) {
          end
        } else {
          val m = begin + (end - begin) / 2
          if (k <= a(m)) lowerBound(begin, m) else lowerBound(m, end)
        }
      }

      lowerBound(-1, a.length)
    }

    var even = true
    for (x <- am) {
      val i1 = lowerBound(bm, t - x)
      val i2 = lowerBound(bm, 2 * t - x)
      val i3 = lowerBound(bm, 3 * t - x)
      val i4 = lowerBound(bm, 4 * t - x)
      if ((((i2 - i1) + (i4 - i3)) & 1) == 1) {
        even = !even
      }
    }

    if (!even) {
      ans += t
    }
  }

  println(ans)
}

class FastScanner(source: java.io.InputStream) {
  val buf = new Array[Byte](1024)
  var now, end = 0

  def isPrintable(b: Byte): Boolean = 33 <= b && b <= 126
  def isNum(b: Byte): Boolean = 48 <= b && b <= 57

  def hasNextByte: Boolean = {
    if (now < end) {
      true
    } else {
      now = 0
      end = source.read(buf)
      end > 0
    }
  }

  def nextByte(): Byte = {
    if (hasNextByte) {
      val b = buf(now)
      now += 1
      b
    } else {
      -1
    }
  }

  def hasNext: Boolean = {
    while (hasNextByte && !isPrintable(buf(now))) {
      now += 1
    }
    hasNextByte
  }

  def next(): String = {
    if (hasNext) {
      val sb = new StringBuilder()
      var b = nextByte()
      while (isPrintable(b)) {
        sb += b.toChar
        b = nextByte()
      }
      sb.toString
    } else {
      throw new NoSuchElementException()
    }
  }

  def nextInt(): Int = {
    nextLong().toInt
  }

  def nextLong(): Long = {
    if (hasNext) {
      var b = nextByte()
      var sign = 1
      var n = 0L
      if (b == '-') {
        sign = -1
        b = nextByte()
      }
      while (isNum(b)) {
        n = n * 10 + (b - 48)
        b = nextByte()
      }
      sign * n
    } else {
      throw new NoSuchElementException()
    }
  }

  def nextDouble(): Double = next().toDouble
}


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

const ll mod = 1000000007;

int main(void)
{
	ll s, w;
	cin >> s >> w;
	if (w >= s) {
		cout << "unsafe" << endl;
	}
	else {
		cout << "safe" << endl;
	}
	return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;
/* ちゃんと考えてわかって実装 */

int main(void){
    int n, x, y;
    cin >> n >> x >> y;

    vector<int> d(n);
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            // x, y間を通過する場合と通過しない場合の小さい方
            // 通過しない -> j - i
            // 通過する -> abs(i-x) + 1 + abs(j-y)
            int path = min(j-i, abs(i-x) + 1 + abs(j-y));
            d[path]++;
        }
    }

    for(int i=1; i<=n-1; i++){
        cout << d[i] << endl;
    }

    return 0;
}

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

#define ASC(a) a.begin(), a.end()		// 昇順ソート 例：sort(ASC(a));
#define DESC(a) a.rbegin(), a.rend()	// 降順ソート 例:sort(DESC(a));
#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, n) for(int i = 1; i < n; i++)
#define In(a) rep(i, n) cin>>a[i];
#define ANS(s) cout << s << endl
#define inc(a, b) cin >> a >> b;
#define only_unique(vec) vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }


// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
//int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
//int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };


// ────────────────────────────────────────────────────

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

	int x; cin >> x;
	vii a(x);
	rep(i, x) cin >> a[i].first;

	int y; cin >> y;
	vii b(y);
	rep(i, y) cin >> b[i].first;

	int z; cin >> z;
	vii c(z);
	rep(i, z) cin >> c[i].first;

	rep(i, z) {
		rep(j, x) {
			if (c[i].first == a[j].first) c[i].second -= 1;
		}

		rep(j, y) {
			if (c[i].first == b[j].first) c[i].second += 1;
		}
	}

	int cnt = 0;
	rep(i, z) {
		if (c[i].second >= 0) cnt++;
	}
	
	cout << cnt << endl;
}


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

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

constexpr int MAX_N = 100;
constexpr int MAX_W = 1e5;

long long dp[MAX_N+1][MAX_W+1];
int w[MAX_N], v[MAX_N];

int main() {
  int N, W;
  cin >> N >> W;
  for (int i{}; i < N; ++i)
    cin >> w[i] >> v[i];

  for (int i{}; i < N; ++i) {
    for (int j{}; j <= W; ++j) {
      dp[i+1][j] = dp[i][j];
      if (j >= w[i])
        chmax(dp[i+1][j], dp[i][j-w[i]] + v[i]);
    }
  }

  cout << dp[N][W] << endl;
  return 0;
}


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

int main(void){
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    double value = (v.at(0) + v.at(1)) / 2.0;
    for(int i = 2; i < n; i++){
        value = (value + v.at(i)) / 2.0;
    }
    cout << value << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main() {
    Scanner(System.`in`).use { scanner ->
        val k = scanner.nextInt()
        val s = scanner.next()
        val omitted = omitted(k, s)
        println(omitted)
    }
}

fun omitted(k: Int, s: String): String {
    if (s.length <= k) return s
    return s.slice(0 until k) + "..."
}

Measured memory_bytes: 37940
s = input()
ans = "NA"
c = 0
#YYMM
if 0<=int(s[:2])<=99 and 1<=int(s[2:])<=12:
  ans = "YYMM"
  c += 1
#MMYY
if 1<=int(s[:2])<=12 and 0<=int(s[2:])<=99:
  ans = "MMYY"
  c+=1
if c == 2:
  ans = "AMBIGUOUS"
print(ans)

Measured memory_bytes: 3064
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 105
#define fi(a, b, c) for(int a = (b); a < (c); a++)
#define FI(a, b, c) for(int a = (b); a <= (c); a++)
using namespace std;

int n, m, c[26], c4, c2, c1;
char s[N];

int main(){
	scanf("%d %d", &n, &m);
	
	fi(i, 0, n){
		scanf("%s", s);
		fi(j, 0, m){
			c[s[j] - 'a']++;
		}
	}
	
	c4 = (n / 2) * (m / 2);
	c2 = (n % 2) * (m / 2) + (m % 2) * (n / 2);
	c1 = (n % 2) * (m % 2);
	
	fi(i, 0, 26) {
		int h = min(c4, c[i] / 4);
		c[i] -= h * 4;
		c4 -= h;
	}
	
	fi(i, 0, 26) {
		int h = min(c2, c[i] / 2);
		c[i] -= h * 2;
		c2 -= h;
	}
	
	fi(i, 0, 26) {
		int h = min(c1, c[i]);
		c[i] -= h;
		c1 -= h;
	}
	
	if(c1 || c2 || c4) puts("No");
	else puts("Yes");
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define RREP(i,a,b) for (int i = a; i > (b); --i)
#define all(x) (x).begin(),(x).end()
const long long INF = 1000000007;
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
int bfs(Graph &G,int sx, int sy,int w){
  vector<int>dist(10000,-1);
  queue<int>que;
  int n = (sy * w) + sx;
  dist[n] = 0;
  que.push(n);
  while(!que.empty()){
    int v = que.front();
    que.pop();
    for(auto nv : G[v]){
      if(dist[nv] != -1)continue;
      dist[nv] = dist[v] + 1;
      que.push(nv);
    }
  }
  int res = 0;
  rep(i,1000)res = max(res,dist[i]);
  return res;
}
int h,w;
int solve(){
  cin >> h >> w;
  Graph G(h * w);
  vector<string>s(h + 1);
  rep(i,h){
    string tmp;
    cin >> tmp;
    tmp.push_back('#');
    s[i] = tmp;
  }
  string tmp;
  rep(i,w)tmp.push_back('#');
  s[h] = tmp;
  rep(i,h)rep(j,w){
    if(s[i][j] == '#')continue;
    int now = (i * w) + j;
    if(s[i + 1][j] != '#'){
      G[now].push_back(now + w);
      G[now + w].push_back(now);
    }
    if(s[i][j + 1] != '#'){
      G[now + 1].push_back(now);
      G[now].push_back(now + 1);
    }
  }
  int ans = 0;
  rep(i,h)rep(j,w){
    if(s[i][j] == '#')continue;
    ans = max(ans,bfs(G,j,i,w));
  }
  cout << ans << endl;
  return 0;
}
int main(){
  ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define print(s) cout << s << endl
#define acc(v) accumulate(v.begin(), v.end(), 0)
#define cinv(n, v) rep(i, n) cin >> v[i]
using namespace std;
const int INF = 1e9;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vchar;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
int x_pos[4] = {1, 0, -1, 0}, y_pos[4] = {0, 1, 0, -1};
int ctoi(char c)
{
	if (c >= '0' && c <= '9')
	{
		return c - '0';
	}
	return 0;
}

char upper(char c)
{
	return c - 0x20;
}

char lower(char c)
{
	return c + 0x20;
}

void unique_vector(vector<int> &v)
{
	sort(all(v));
	v.erase(unique(all(v)), v.end());
}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val)
{
	std::fill((T *)array, (T *)(array + N), val);
}

//ユークリッドの互除法
//最大公約数
ll gcd(ll x, ll y)
{
	if (y == 0)
		return x;
	return gcd(y, x % y);
}

//最小公倍数
ll lcm(ll x, ll y)
{
	ll g = gcd(x, y);
	return x / g * y;
}

ll myPow(ll x, ll n, ll m)
{
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

//素因数分解
map<ll, ll> prime_factor(ll n)
{
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++)
	{
		while (n % i == 0)
		{
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1)
		ret[n] = 1;
	return ret;
}

int main()
{
	int n;
	cin >> n;
	rep(i,10){
		if(i==0)
			continue;
		if(n%i==0 && n/i < 10){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
s=0
a = [list(input().split())for i in range(N)]
for i in range(N):
    del a[i][0]
    a[i]=set(a[i])
c=a[0]
for i in range(N):
    c=c&a[i]
print(len(c))


Measured memory_bytes: 3060
n = int(input())
s = [-1]
s.extend(list(map(int,input().split())))
q = int(input())
lfin=list(map(int,input().split()))
ans = 0

for item in lfin:
    ok = n
    ng = 0
    while(abs(ok-ng)>1):
        num = (ok+ng)//2
        if s[num] >= item:
            ok = num
        else:
            ng = num
    else:
        if s[ok] == item:
            ans += 1
print(ans)


Measured memory_bytes: 16708
#include<stdio.h>
 
int main(void)
{
  int N, i, j, k, v;
  scanf("%d",&N);
  int A[N];
  for(i = 0; i < N ;i++)
  {
    scanf("%d",&A[i]);
    printf("%d",A[i]);
    if (i < N-1)
    {
      printf(" ");
    }
    else
    {
      printf("\n");
    }
  }
  for(i = 1; i < N; i++)
  {
    v = A[i];
    j = i - 1;
    while(j  > -1 && A[j] > v)
    {
      A[j + 1] = A[j];
      j--;
      A[j + 1] = v;
    }
    for(k = 0; k < N; k++)
    {
      if(k > 0)
      {
        printf(" ");
      }
      printf("%d",A[k]);
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 604
//I am so vegetable
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define PB push_back
#define IN insert
#define ER erase
#define CT count
#define EP empty
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const double eps = 1e-6;
const double pi = 3.141593;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; }return ans; }
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
ll inv(ll x, int mod = MOD) { return qpow(x, mod - 2) % mod; }
ll m_m(ll a){ return (a%MOD+MOD)%MOD; }
int main() {
	//ofstream cout("E:\\acm dream\\out.txt",ios::out);
	FIO;
	int a,b;cin>>a>>b;
	if(a<=b)cout<<"unsafe\n";
	else cout<<"safe\n";
	return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 400100;
struct edges
{
	int to, next;
}edge[maxn << 1];
int point[maxn] = {0}, te = 0;
void add(int a, int b)
{
	te ++;
	edge[te].to = b;
	edge[te].next = point[a];
	point[a] = te;
}
int dfs3(int now, int p, int lim)
{
	if(now > lim)
		return 0;
	int ans = 1;
	for(int e = point[now]; e; e = edge[e].next)
		if(edge[e].to != p)
			ans += dfs3(edge[e].to, now, lim);
	return ans;
}
int n, par[maxn], c[maxn], con[2][maxn] = {0}, a[maxn];
void dfs1(int now, int p, int mx)
{
	par[now] = p;
	mx = max(mx, now);
	a[now] = mx;
	for(int e = point[now]; e; e = edge[e].next)
		if(edge[e].to != p)
			dfs1(edge[e].to, now, mx);
}
void dfs2(int now, int p)
{
	for(int e = point[now]; e; e = edge[e].next)
		if(edge[e].to != p)
			dfs2(edge[e].to, now);
	con[0][now] = 1;
	if(now < a[p])
	{
		for(int e = point[now]; e; e = edge[e].next)
			if(edge[e].to != p)
			{
				if(edge[e].to < a[p])
					con[1][edge[e].to] = con[0][edge[e].to];
				else
					con[1][edge[e].to] = 0;
				con[0][now] += con[1][edge[e].to];
			}
	}
	else
	{
		for(int e = point[now]; e; e = edge[e].next)
			if(edge[e].to != p)
			{
				con[1][edge[e].to] = dfs3(edge[e].to, now, a[p]);
				con[0][now] += con[1][edge[e].to];
			}
	}
}
void dfs4(int now, int p)
{
	if(now > a[par[p]])
		c[now] = c[p] + con[0][now];
	else
		c[now] = c[p] + con[0][now] - con[1][now];
	for(int e = point[now]; e; e = edge[e].next)
		if(edge[e].to != p)
			dfs4(edge[e].to, now);
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	dfs1(1, 0, 0);
	dfs2(1, 0);
	c[1] = 1;
	for(int e = point[1]; e; e = edge[e].next)
		dfs4(edge[e].to, 1);
	for(int i = 2; i <= n; i ++)
		cout << c[i] - 1 << " " ;
	cout << endl;
	return 0;
}

Measured memory_bytes: 24576
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);

typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long int ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vp;
typedef pair<int,pair<int,int>> ddp;
typedef pair<long long,pll> ldp;

#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(), v.end()
#define FI(n) for(int i=0;i<(n);++i)
#define FJ(n) for(int j=0;j<(n);++j)
#define FK(n) for(int k=0;k<(n);++k)
#define FL(n) for(int l=0;l<(n);++l)
#define FQ(n) for(int q=0;q<(n);++q)
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(1.0 * (x))
#define pow(x, n) pow(1.0 * (x), n)
#define PI          3.14159265358979323846264
#define mod         1000000007
int MAX = 100000+5;

int main()
    {
        fastio
      /*  int t;
        cin >> t;
        while(t-->0)
        {
            
        }
        */
        int n,p;
        cin >> n >> p;
        n=n*3;
        int x=n+p;
        cout << x/2;
        return 0;
        return 0;
    }

Measured memory_bytes: 256
#include <algorithm>
// #include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double db;
const int oo=2139063143;
const int N=2010000;
const int P=1000000007;
const db eps=1e-7;
#define pritnf printf
//char buf[1<<22],*p1=buf,*p2=buf,obuf[1<<22],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
    if (x< 0) putchar('-'),x=-x;
    if (x>=10) print(x/10);
    putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
template <typename T1,typename T2>
void chkmax (T1 &A,T2 B) { A=A>=B?A:B; }
template <typename T1,typename T2>
void chkmin (T1 &A,T2 B) { A=A<=B?A:B; }
int n,m,k,a[N],b[N],c[N],d[N];
struct LY { int i,x; }st[N],l[N]; int z=0,cnt=0;
char sa[N],sb[N];
int main ()
{
    // freopen (".in","r",stdin);
    // freopen (".out","w",stdout);
	sc(n),sc(m),sc(k);
	scanf ("%s%s",sa+1,sb+1);
	for (int i=1; i<=n; i++)
		a[i]=sa[i]-'0';
	for (int i=1; i<=m; i++)
		b[i]=sb[i]-'0';
	reverse (a+1,a+n+1),reverse (b+1,b+m+1);
	for (int i=max (n,m); i>=1; i--) if (a[i]&&b[i])
	{
		int las=k,x=3,pos=i;
		while (z)
		{
			if (x==3)
			{
				int g=st[z].i-pos;
				if (g> las) break;
				las-=g,pos=st[z].i;
				l[++cnt]=(LY){pos,x^st[z].x};
				x&=st[z].x;
			}
			else if (x)
			{
				if (st[z].i!=pos+1) break;
				pos=st[z].i;
				if (x^st[z].x) x=3;
				else x&=st[z].x;
			}
			else break;
			--z;
		}
		if (x==3) pos+=las,c[pos]=d[pos]=1;
		else if (x) l[++cnt]=(LY){++pos,x};
		while (cnt) st[++z]=l[cnt--];
	}
	else if (a[i]||b[i]) st[++z]=(LY){i,a[i]*2+b[i]};
	for (int i=1; i<=z; i++)
		c[st[i].i]=st[i].x>>1,d[st[i].i]=st[i].x&1;
	n=m=max (n,m)+k;
	while (!c[n]) --n;
	while (n) putchar(c[n--]+'0');
	putchar('\n');
	while (!d[m]) --m;
	while (m) putchar(d[m--]+'0');

    return 0;
}


Measured memory_bytes: 37888
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numIn;
        int sum;
        int numPattern;
        int i, j, k;
        while (true) {
            numIn = sc.nextInt();
            sum = sc.nextInt();
            numPattern = 0;
            if (numIn == 0 && sum == 0) break;
            for (i = 1; i <= numIn; i++) {
                for (j = i + 1; j <= numIn; j++) {
                    for (k = j + 1; k <= numIn; k++) {
                        if (i + j + k == sum) numPattern += 1;
                    }
                }
            }
            System.out.println(numPattern);
        }
    }
}



Measured memory_bytes: 26748
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here! 
        char a = 'a';
        int[] table = new int[26];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        StringBuilder sb = new StringBuilder();
        while((line = br.readLine()) != null){
            sb.append(line);
        }
        String lines = new String(sb);
        char[] arr = lines.toLowerCase().toCharArray();
        
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<26; j++){
                if(arr[i]==(char)(a+j)){
                    table[j] += 1;
                    break;
                }
            }
        }
        
        for(int i=0; i<26; i++) {
            System.out.println((char)(a+i) + " : " + String.valueOf(table[i]));
        }
    }
}



Measured memory_bytes: 24252
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;
const int mod = MOD7;

void ERROR(int num) { printf("ERROR%d!\n",num); }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};


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

    int N;
    cin >> N;
    vector<ll> A;
    A.resize(N);
    rep(i,N) cin >> A[i];

    map<ll,pair<ll,ll>> Map;
    vector<int> memo;

    rep(i,N){
      int num = A[i];
      if(Map[num].first==0) memo.pb(num);
      Map[num].second += Map[num].first;
      Map[num].first++;
    }

    ll total = 0;
    rep(i,memo.size()){
      ll num = memo[i];
      Map[num].first--;
      total += Map[num].second;
    }

    rep(i,N){
      ll num = A[i];
      //cout << Map[num].first << " " << Map[num].second << endl;
      cout <<  total-Map[num].first << endl;
      //cout << endl;
    }

}

Measured memory_bytes: 11640
#include<iostream>

#define     MIN_POINT     0
#define     MAX_POINT     100

using namespace std;

int main(){
	int *taro_cards_p, *hanako_cards_p;
	int taro, hanako;

	// ループ
	cin >> taro >> hanako;
	while((taro > 0) || (hanako > 0)){
		int taro_cards[((MAX_POINT)-(MIN_POINT)+1)] = {};
		int hanako_cards[((MAX_POINT)-(MIN_POINT)+1)] = {};
		int taro_sum = 0, hanako_sum = 0;
		int d, buf, i, a = ((int)(MAX_POINT)) + 1, b = ((int)(MAX_POINT)) + 1;

		// メモリ領域の確保
		taro_cards_p = new int[taro];
		hanako_cards_p = new int[hanako];
		// 確保できたかチェック
		if((taro_cards_p == NULL) || (hanako_cards_p == NULL)){
			cerr << "メモリ領域の確保に失敗しました" << endl;
			return -1;
		}

		// 太郎のカードの入力
		for(i=0;i<taro;i++){
			cin >> buf;
			if((buf < ((int)(MIN_POINT))) || (buf > ((int)(MAX_POINT)))){
				cerr << "入力された値が範囲外です" << endl;
				i--;
				continue;
			}
			taro_cards_p[i] = buf;
			taro_cards[buf]++;
			taro_sum += buf;
		}
		// 花子のカードの入力
		for(i=0;i<hanako;i++){
			cin >> buf;
			if((buf < ((int)(MIN_POINT))) || (buf > ((int)(MAX_POINT)))){
				cerr << "入力された値が範囲外です" << endl;
				i--;
				continue;
			}
			hanako_cards_p[i] = buf;
			hanako_cards[buf]++;
			hanako_sum += buf;
		}
		// 太郎の合計 - 花子の合計
		d = taro_sum - hanako_sum;
		// 条件を満たすカードの組が存在するかチェック その1
		if((((d < 0) ? (d * (-1)) : d) % 2) != 0){
			// メモリ領域の解放
			delete [] taro_cards_p;
			delete [] hanako_cards_p;
			// 結果の表示
			cout << "-1" << endl;
			// 入力
			cin >> taro >> hanako;
			// ループの残りの処理を飛ばす
			continue;
		}
		// 条件を満たすカードが存在するとき、あるカードに対応する
		// もう片方のカードが何であるべきかを求める
		// そして、条件を満たすカードの組を求める
		if(taro <= hanako){
			for(i=0;i<taro;i++){
				if(hanako_cards[((taro_cards_p[i]) - (d / 2))] > 0){
					if(((taro_cards_p[i] * 2) - (d / 2)) < (a + b)){
						a = taro_cards_p[i];
						b = (taro_cards_p[i]) - (d / 2);
					}
				}
			}
		}else{
			for(i=0;i<hanako;i++){
				if(taro_cards[((hanako_cards_p[i]) + (d / 2))] > 0){
					if(((hanako_cards_p[i] * 2) + (d / 2)) < (a + b)){
						a = hanako_cards_p[i] + (d / 2);
						b = hanako_cards_p[i];
					}
				}
			}
		}
		// メモリ領域の解放
		delete [] taro_cards_p;
		delete [] hanako_cards_p;
		// 出力
		if((a == (((int)(MAX_POINT)) + 1)) && (b == (((int)(MAX_POINT)) + 1))){
			cout << "-1" << endl;
		}else{
			cout << a << " " << b << endl;
		}
		// 入力
		cin >> taro >> hanako;
	}

	return 0;
}

Measured memory_bytes: 1200
import Control.Monad
import Control.Monad.Primitive (PrimState)
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Data.IORef

main :: IO ()
main = do
    n <- fst . fromJust . B.readInt <$> B.getLine
    as <- V.fromList . map (fst . fromJust . B.readInt) . B.words <$> B.getLine
    mv <- MV.unsafeNew (n + 1) :: IO (MV.MVector (PrimState IO) Int)
    l <- newIORef (n `div` 2)
    r <- newIORef (n `div` 2 + 1)
    forM_ [0..(n - 1)] $ \i ->
        if i `mod` 2 == (n - 1) `mod` 2
            then do
                m <- readIORef l
                MV.unsafeWrite mv m (as V.! i)
                modifyIORef l pred
            else do
                m <- readIORef r
                MV.unsafeWrite mv m (as V.! i)
                modifyIORef r succ
    j <- readIORef l
    v <- V.unsafeFreeze $ MV.slice (j + 1) n mv
    B.putStrLn $ B.unwords $ map (B.pack . show) $ V.toList v


Measured memory_bytes: 36092
import java.util.Scanner;
public class Main{
public static void main(String[] args){
	Scanner sc= new Scanner(System.in);
	int N = sc.nextInt();
	String S = sc.next();

	int halfN = N/2;



	//文字列の前半
	String halfS1 = S.substring(0,halfN);
	String result = halfS1+halfS1;

	//一致の確認と出力
	if(result.equals(S)){
		System.out.println("Yes");
	}
		else{
			System.out.println("No");
		}
	}
}



Measured memory_bytes: 21840
#include<bits/stdc++.h>
using namespace std;
int n;
string str[10100];
int res;
int oa,ob,bb;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>str[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<str[i].size()-1;j++)
			if(str[i][j]=='A'&&str[i][j+1]=='B'){
				res++;
			}
		if(str[i][str[i].size()-1]=='A'){
			if(str[i][0]=='B')
				bb++;
			else
				oa++;
		}
		else if(str[i][0]=='B')
			ob++;
	}
	if(bb!=0)
		res+=(bb-1);
	if(oa!=0&&bb!=0){
		res++;
		oa--;
	}
	if(ob!=0&&bb!=0){
		res++;
		ob--;
	}
	res+=min(oa,ob);
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 768
H,W = map(int,input().split())
a = list(list(map(int,input().split()))for i in range(H))
ans=[]
for i in range(H):
    for j in range(W-1):
        if a[i][j]%2==1:
            ans.append([i+1,j+1,i+1,j+2])
            a[i][j+1] += 1
for i in range(H-1):
    if a[i][W-1]%2 == 1:
        ans.append([i+1,W,i+2,W])
        a[i+1][W-1] += 1
print(len(ans))
for a,b,c,d in ans:
    print(a,b,c,d)


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

using namespace std;

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

#define ALL(obj)	(obj).begin(),(obj).end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

typedef pair<int,int>			P;
typedef vector<int>				V;
typedef vector<V>				VV;

template<typename T>string join(const v(T)&v)
{stringstream s;REP(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define MAX 		40010

const ll LINF = (ll)1e18+7;		//
const int INF = 1e9+7;			//2,147,483,647 (Max int)
const ll MOD = 1e9+7;
// テンプレ終了
//====================================================================//




//
int main(){
	int N,M;cin>>N>>M;
	priority_queue<int> A;
	ll ans = 0;
	REP(i,N){
		int t;cin>>t;
		A.push(t);
		ans += t;
	}
	
	REP(i,M){
		int t=A.top();A.pop();
		ans -= (ll)ceil((double)t/2);
		A.push(floor((double)t/2));
	}

	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 892
#include <stdio.h>
int main(void){
    int a,b,c,d;
    int e,f,g;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    e=b-a;
    f=c-b;
    g=c-a;
    if(e<0){
        e=a-b;
    }
    if(f<0){
        f=b-c;
    }
    if(g<0){
        g=a-c;
    }
    if(g<=d){
        printf("Yes");
        return 0;
    }
    if(e<=d&&f<=d){
        printf("Yes");
    }
    else{
        printf("No");
    }
}

Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
#define rep(i, a, n) for (int i = (a); i < (n); i++)
#define repr(i, n, a) for (int i = (n)-1; i >= (a); i--)
#define each(it, v) for (auto(it) = (v).begin(); (it) != (v).end(); (it)++)
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vi>
#define vd vector<double>
#define vvd vector<vd>
#define co(x) cout << (x)
#define con(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define out(x) rep(i, 0, (x).size()) cout << (x)[i] << ((i != (x).size() - 1) ? " " : "\n")
const double PI = 3.14159265;
const int MAXN = 1 << 15;
const ll LINF = 1LL << 60;
const int INF = 1 << 30;
#define Pr(a) (#a) << "=" << (a) << " "
#define pr(a) cout << Pr(a) << '\n'
///////////////////////////////////////////////////////
int main() {
  int n;
  cin >> n;
  set<int> S;
  rep(i, 0, n) {
    int a;
    cin >> a;
    S.insert(a);
  }
  int q;
  cin >> q;
  while (q--) {
    int k;
    cin >> k;
    int ans = S.count(k);
    cout << ans << '\n';
  }

  return 0;
}


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

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll INF = 1LL << 60;

//input
int K;
string S;

//dpTable

int main(){
    cin >> K >> S;
    if (K >= S.size()) cout << S << endl;
    else {
        rep (i,K){
            cout << S.at(i);
        }
        cout << "..." << endl;
    }
}

Measured memory_bytes: 3620
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""

input:
5 4
0 1
1 2
2 3
3 4

output:
1
2
3
"""

import sys

sys.setrecursionlimit(int(1e5))


def dfs_Tarjan(current):
    global timer
    children = 0
    visited[current] = True
    disc[current] = low[current] = timer
    timer += 1

    for adj in adj_table[current]:
        if not visited[adj]:
            parent[adj] = current
            children += 1
            dfs_Tarjan(adj)
            low[current] = min(low[current], low[adj])
            if parent[current] == -1 and children > 1:
                art_set.add(current)
            elif parent[current] != -1 and low[adj] >= disc[current]:
                art_set.add(current)

        elif adj != parent[current]:
            low[current] = min(low[current], disc[adj])

    return None


def dfs_init():
    for v in range(v_num):
        if not visited[v]:
            dfs_Tarjan(v)

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    adj_table = tuple([] for _ in range(v_num))
    for edge in edges:
        source, target = map(int, edge)
        adj_table[source].append(target)
        adj_table[target].append(source)

    timer = 0
    art_set = set()
    parent = [-1] * v_num
    visited = [False] * v_num
    disc, low = ([float('inf')] * v_num for _ in range(2))

    dfs_init()
    if art_set:
        print(*sorted(art_set), sep='\n')

Measured memory_bytes: 23708
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int n, k;
vector<vector<int>> e(100010);
ll ans;

void dfs(int now, int parent) {
    int color_num;
    if (now == 0) color_num = k - 1;
    else color_num = k - 2;
    for (auto i : e[now]) {
        if (i == parent) continue;
        dfs(i, now);
        ans *= color_num;
        ans %= MOD;
        color_num--;
    }
}

int main() {
    cin >> n >> k;
    rep(i, 0, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    ans = k;
    dfs(0, -1);
    cout << ans << endl;
    return 0;
}


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

int N;

int main() {
  cin >> N;
  for(int i =0 ; i < N; i++) {
    int tmp;
    cin >> tmp;
    if(tmp % 2 == 0 && !(tmp % 3 == 0 || tmp%5 == 0)) {
      cout << "DENIED";
      return 0;
    }
  }
  cout << "APPROVED";
}


Measured memory_bytes: 256
import java.util.*;

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();
    if(A-B>C){
     System.out.println(0);
    }else{
     System.out.println(C-(A-B));
    }
  }
}



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


int main(void) {
	int h, w, k, i, j, l, dp[103][10] = {};
	const int mod = 1e9 + 7;

	cin >> h >> w >> k;

	dp[0][0] = 1;
	for (i = 1; i <= h; i++) {
		for (j = 0; j < (1 << (w - 1)); j++) {
			for (l = 0; l < w - 2; l++) {
				if (((j >> l) & 1) == 1 && ((j >> (l + 1)) & 1) == 1) {
					break;
				}
			}
			if (l < w - 2) continue;
			for (l = 0; l < w; l++) {
				int& dpn = dp[i][l];
				if (l > 0 && ((j >> (l - 1)) & 1) == 1) {
					dpn = (dpn + dp[i - 1][l - 1]) % mod;
				}
				else if (l < w - 1 && ((j >> l) & 1) == 1) {
					dpn = (dpn + dp[i - 1][l + 1]) % mod;
				}
				else {
					dpn = (dpn + dp[i - 1][l]) % mod;
				}
			}
		}
	}

	cout << dp[h][k - 1] << endl;

	return 0;
}

Measured memory_bytes: 256
import math
N=int(input())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
p=[]
for i in range(N):
    x[i],y[i]=map(int,input().split())
    p.append((x[i],y[i]))
def dist(p,q):
    a,b=p
    c,d=q
    return math.sqrt((a-c)**2+(b-d)**2)
def check(R):
    Q=[]
    for i in range(N):
        for j in range(i+1,N):
            d=dist(p[i],p[j])/2
            if R<d:
                return False
            h=math.sqrt(R*R-d*d)
            #print(d,h,R)
            nx,ny=(x[j]-x[i],y[j]-y[i])
            nr=math.sqrt(nx**2+ny**2)
            dx,dy=h*nx/nr,h*ny/nr
            mx,my=(x[i]+x[j])/2,(y[i]+y[j])/2
            #print(mx,my)
            #print(dx,dy)
            Q.append((mx+dy,my-dx))
            Q.append((mx-dy,my+dx))
    #print(Q,R)
    for pa in Q:
        flag=1
        for i in range(N):
            #print(pa,i,dist(pa,p[i]),R)
            if dist(pa,p[i])>R+9e-7:
                flag=0
                break
        if flag==1:
            return True
    return False

low=0
high=2000
for line in range(50):
    mid=(low+high)/2
    if check(mid):
        high=mid
    else:
        low=mid
print(mid)
    

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

int main(){
    int64_t a,b;
    cin >> a >>b;
    int64_t g = min(a, b);
    while(!(a%g == 0 && b%g == 0)){
        g --;
    }
    cout << a*b/g << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if (a<b)
		cout<<"a < b"<<endl;
	else if (a>b)
		cout<<"a > b"<<endl;
	else
		cout<<"a == b"<<endl;
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> V(N);
  for (int i = 0; i < N; i++) cin >> V.at(i);
  cout << accumulate(V.begin(), V.end(), 0) - *max_element(V.begin(), V.end()) / 2 << endl;
}

Measured memory_bytes: 256
N,M=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(M)] 
*p,=map(int,input().split())
t=0
a=0
for i in range(2 ** N):
 t=sum(1 for j in range(M) if sum(1 for h in k[j][1:] if i>>(h-1)&1)%2==p[j])
 if t==M:a+=1
print(a)

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

int main() {
  int N;
  int s=0;
  cin >> N;
  int w=N;
  for (int i = 0; i < N; i++) {
    s+=w%10;
    w/=10;
    if(w==0)
      break;
  }
  if(N%s==0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-6;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int main(void){
	int32 N;
	while(cin >> N && N){
		int32 W, H;
		cin >> W >> H;
		vector<vector<int32>> f(H+1, vector<int32>(W+1, 0));
		int32 x, y;
		REP(i, N){
			cin >> x >> y;
			f[y][x] = 1;
		}
		FOR(i, 1, H+1){
			FOR(j, 1, W+1){
				f[i][j] += f[i-1][j]+f[i][j-1]-f[i-1][j-1];
			}
		}
		int32 S, T;
		cin >> S >> T;
		int32 res = 0;
		FOR(i, 0, H-T+1){
			FOR(j, 0, W-S+1){
				res = max(res, f[i+T][j+S]-f[i][j+S]-f[i+T][j]+f[i][j]);
			}
		}
		cout << res << endl;
	}
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[202020];
int B[202020];
ll S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int dif=0;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		if(A[i]!=B[i]) dif=1;
		S+=A[i];
	}
	if(dif==0) return _P("0\n");
	ll ret=0;
	vector<ll> cand;
	FOR(i,N) {
		if(A[i]<=B[i]) ret+=B[i];
		else cand.push_back(B[i]);
	}
	sort(ALL(cand));
	reverse(ALL(cand));
	FOR(i,cand.size()-1) ret+=cand[i];
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
    for(int n; cin >> n && n;)
	{
		vint v(n);
		rep(i, n) cin >> v[i];
		
		int m = 32;
		for(int i = 0; 0 < m; i++)
		{
			cout << (m -= (m - 1) % 5) << endl;
			cout << (max(0, m -= v[i % n])) << endl;
		}
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
#define S second
#define F first
const int  MOD = 1e9 + 7;
const int  N = 1007;
char g[N][N];
ll dp[N][N];

//  a d f j k  l  ;
int main(){
    ios::sync_with_stdio(0);  cin.tie(0);
    int H , W;
    cin>>H>>W;
    for(int i = 0 ; i < H ; i++){
        for(int j = 0 ; j < W ; j++){
            cin>>g[i][j];
        }
    }
    dp[0][0] = 1;
    for(int i = 0 ; i < H ; i++){
        for(int j = 0 ; j < W ; j++){
            if( (i == 0 && j == 0) || g[i][j] == '#') continue;
            if(i > 0) dp[i][j] += dp[i-1][j];
            if(j > 0) dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
    }
    cout<<dp[H-1][W-1]<<endl;


    return 0;
}

Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;cin>>N>>K;
  vector<int> p(N);
  for(int i=0;i<N;i++)cin>>p[i];
  sort(p.begin(),p.end());
  int sum=0;
  for(int i=0;i<K;i++)sum+=p[i];
  cout<<sum<<endl;
}


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

using namespace std;

int main(){
    int N; cin>>N;
    int M; cin>>M;
    int LN,RN;//加減上限
    vector<int> L(M);
    vector<int> R(M);
    for(int i=0;i<M;i++){
        cin>>L[i];
        cin>>R[i];
    }
    LN=1;
    RN=N;
    for(int i=0;i<M;i++){
        if(L[i]>LN) LN=L[i];
        if(R[i]<RN) RN=R[i];
        if(LN>RN){
            RN=LN-1;
            break;
        }
    }
    printf("%d",RN-LN+1);

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100001,INF=1<<30;
vector<int> S[MAX];
int N,ord[MAX],low[MAX],visit[MAX],par[MAX],timer;

void DFS(int cur,int mae){
    
    ord[cur]=low[cur]=timer;
    par[cur]=mae;
    visit[cur]=1;
    timer++;
    
    for(int i=0;i<S[cur].size();i++){
        int a=S[cur][i];
        if(a==mae) continue;
        if(visit[a]){
            low[cur]=min(low[cur],ord[a]);
            continue;
        }
        DFS(a,cur);
        low[cur]=min(low[cur],low[a]);
    }
}

void search(int u){//u==0なら関節点、1なら橋
    for(int i=0;i<N;i++){
        visit[i]=0;
        par[i]=-1;
    }
    timer=1;
    
    DFS(0,-1);
    
    if(u==0){
        set<int> se;
        int cnt=0;
        for(int i=1;i<N;i++){
            if(par[i]==0) cnt++;
            else if(ord[par[i]]<=low[i]) se.insert(par[i]);
        }
        if(cnt>1) se.insert(0);
        
        for(auto it=se.begin();it!=se.end();it++){
            cout<<*it<<endl;
        }
    }else{
        set<pair<int,int>> se;
        for(int i=0;i<N;i++){
            for(int j=0;j<S[i].size();j++){
                if(ord[i]<low[j]){
                    int a=i,b=j;
                    if(a>b) swap(a,b);
                    se.insert(make_pair(a,b));
                }
            }
        }
        
        for(auto it=se.begin();it!=se.end();it++){
            cout<<(*it).first<<" "<<(*it).second<<endl;
        }
    }
}

int main(){

    int M;cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        S[a].push_back(b);
        S[b].push_back(a);
    }
    
    search(0);
}




Measured memory_bytes: 6960
N, M, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

s = 0
MA = -1
for i in range(N):
  s += A[i]
  if s > K:
    MA = i
    s -= A[i]
    break
if MA < 0:
  MA = N

  
ans = MA
MB = 0
while MB < M:
  while True:
    if MB < M and s + B[MB] <= K:
      s += B[MB]
      MB += 1
      ans = max(ans, MA + MB)
    else:
      break
  if MA > 0:
    s -= A[MA-1]
    MA -= 1
  else:
    break

print(ans)

Measured memory_bytes: 40856
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int N, M;
using Graph = vector<vector<int> >;
bool all_visited;

// visitedは訪問回数
int dfs(Graph &G, int v, bool visited[]) {
  bool all_visited = true;
  for (int i = 0; i < N; i++) {
    if (visited[i] == false) all_visited = false;
  }

  if (all_visited) return 1;
  int ans = 0;

  for (auto next_v : G[v]) {
    if (visited[next_v]) continue;
    visited[next_v] = true;
    ans += dfs(G, next_v, visited);
    visited[next_v] = false;
  }

  return ans;
}

int main() {
  cin >> N >> M;

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

  bool visited[N];
  for (int i = 0; i < N; i++) {
    visited[i] = 0;
  }

  visited[0] = true;
  cout << dfs(G,0,visited) << endl;
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<ll> p(3*N);
    rep(i, 0, 3*N) cin >> p[i];

    sort(p.begin(),p.end());
    reverse(p.begin(),p.end());

    ll ans = 0;
    for(int i = 0, j =1; i < N; j += 2, i++){
        ans += p[j];
    } 
    cout << ans << endl;
}

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

int m;
int x[16], y[16];
int vx[8], vy[8];
int ans;

int cross(int x1, int y1, int x2, int y2) {
	return x1 * y2 - y1 * x2;
}

void dfs(int rem, int pairNum, int depth) {
	if (depth == m / 2) {
		ans = max(ans, pairNum);
		return;
	}
	
	int i, j;
	for (i = 0; i < m; i++) if ((rem >> i) & 1) break;
	for (j = i + 1; j < m; j++) {
		if ((rem >> j) & 1) {
			//connect (Pi, Pj)
			int cnt = 0;
			for (int k = 0; k < depth; k++) {
				if (cross(vx[k], vy[k], x[j] - x[i], y[j] - y[i]) == 0)
					cnt++;
			}
			vx[depth] = x[j] - x[i];
			vy[depth] = y[j] - y[i];
			dfs(rem - (1 << i) - (1 << j), pairNum + cnt, depth + 1);
		}
	}
}

int main() {
	cin >> m;
	for (int i = 0; i < m; i++) cin >> x[i] >> y[i];
	dfs((1 << m) - 1, 0, 0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr,0,sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9+7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int power(int x, int y)
{
    if(y==0) return 1;
    else if(y%2==0)
        return power(x*x%MOD,y/2)%MOD;
    else return (x%MOD*power(x*x%MOD,y/2))%MOD;
}
int solve(int n, int r){
    if(2 * r > n){
        r = n - r;
    }
    int a = 1, b = 1;
    for(int i = 1; i <= r; i++){
        a = (a * (n - i + 1)) % MOD;
        b = (b * i) % MOD;
    }
    return (a * power(b, MOD - 2LL)) % MOD;
}
int32_t  main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n, a, b;
        cin >> n >> a >> b;
        int ans = power(2, n);
        cout << (ans - solve(n, a) - solve(n, b) - 1LL + 3 * MOD) % MOD << '\n';
    } 
}

Measured memory_bytes: 31488