akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
 
int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n,x;
    cin>>n>>x;
    ll w[n],v[n];
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
    }
    ll dp[x+1];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
    {
        for(int j=x;j>=w[i];j--)
        {
            dp[j]=max(dp[j],v[i]+dp[j-w[i]]);
        }
    }
    cout<<dp[x]<<"\n";
}

Measured memory_bytes: 1024
/*
 * sto Qingyu orz
 * 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴,
 * 使其天天爆零
 * 我不由自主地膜拜真神sqy。
 * Author: RainAir
 * Time: 2019-10-17 08:17:33
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 250000 + 5;
const LL ha = 1000000000000000031;
const LL BASE = 1e9+7;

inline LL mul(LL x,LL y){
    __int128_t t = (__int128_t)x*y%ha;
    return (LL)t;
}

inline LL add(LL x,LL y){
    x += y;x %= ha;
    return x;
}

inline LL qpow(LL a,LL n=ha-2){
    LL res = 1;
    while(n){
        if(n & 1) res = mul(res,a);
        a = mul(a,a);
        n >>= 1;
    }
    return res;
}

char str[MAXN];
int n;
LL hsh[MAXN],p[MAXN],inv;
std::map<LL,int> S;

int main(){
    scanf("%d",&n);
    scanf("%s",str+1);inv = qpow(BASE);
    p[0] = 1;//DEBUG(inv);
//    DEBUG(mul(inv,BASE));
    FOR(i,1,n){
        hsh[i] = hsh[i-1];
        p[i] = p[i-1];
        if(str[i] == '+'){
            hsh[i] = add(hsh[i],p[i]);
        }
        if(str[i] == '-'){
            hsh[i] = add(hsh[i],ha-p[i]);
        }
        if(str[i] == '<'){
            p[i] = mul(p[i],inv);
        }
        if(str[i] == '>'){
            p[i] = mul(p[i],BASE);
        }
    }
    LL ans = 0;
    ROF(i,n,1){ // hsh[r]== hsh[n]*base[l-1]+hsh[l-1]
        S[hsh[i]]++;
        ans += S[add(mul(hsh[n],p[i-1]),hsh[i-1])];
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 35584
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;
#define int long long
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
signed main() {
  int N; cin >> N;
  vector<vector<int>> G(N);
  REP(i,N-1) {
    int a, b; cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<int> C(N);
  REP(i,N) {
    cin >> C[i];
  }
  sort(C.rbegin(), C.rend());
  vector<int> A(N, -1);
  queue<int> Q;
  Q.push(0);
  int ptr = 0;
  A[0] = C[ptr++];
  while(!Q.empty()) {
    int v = Q.front();
    Q.pop();
    for(int u : G[v]) {
      if(A[u] != -1) continue;
      A[u] = C[ptr++];
      Q.push(u);
    }
  }
  int sum = accumulate(C.begin() + 1, C.end(), 0LL);
  cout << sum << endl;
  REP(i,N) {
    if (i > 0) cout << ' ';
    cout << A[i];
  }
  cout << endl;
}


Measured memory_bytes: 1152
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#define mod 1000000007
#define pb push_back
using namespace std;
int par[100009];
int ran[100009],p[100009];
int find(int x){
	if(par[x]==x){
		return x;
	}
	else{
		return par[x]=find(par[x]);
	}
}
void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x==y)return;
	if(ran[x]<ran[y]){
		par[x]=y;
	}
	else{
		par[y]=x;
		if(ran[x]==ran[y])ran[x]++;
	}
}
bool same(int x,int y){
	return find(x)==find(y);
}
int main(){
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>p[i];
	}
	for(int i=1;i<=n;i++){
		par[i]=i;
		ran[i]=0;
	}
	for(int i=0;i<m;i++){
		int var1,var2;
		cin>>var1;
		cin>>var2;
		unite(var1,var2);
	}
	for(int i=1;i<=n;i++){
		if(same(i,p[i])){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define MOD 1000000007
//for(int i=0; i<n; ++i)
using namespace std;
#define all(c) c.begin(), c.end()
#define watch(x) cout << (#x) << " is " << (x) << endl
#define ll long long

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

    ll m, k;
    cin >> m >> k;

    if (m == 1)
    {
        if (k == 0)
            cout << "0 0 1 1\n";
        else
            cout << "-1\n";
        return 0;
    }

    if (k >= (1 << m))
    {
        cout << -1 << endl;
        return 0;
    }

    for (ll i = 0; i <= (1ll << m) - 1; ++i)
        if (i != k)
            cout << i << " ";

    cout << k << " ";

    for (ll i = (1ll << m) - 1; i >= 0; --i)
        if (i != k)
            cout << i << " ";

    cout << k << endl;

    return 0;
}

// breaking at 17 131071

Measured memory_bytes: 1792
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iomanip>
using namespace std;
int main()
{
	bool check=true;
	string s;
	int l;
	cin>>s;
	l=s.length();
	if(s[0]!='A') {
		cout<<"WA";
		return 0;
	}
	if(s[1]>='A'&&s[1]<='Z'||s[l-1]>='A'&&s[l-1]<='Z') {cout<<"WA";return 0;}
	for(int i=2;i<l-1;i++)
	{
		if(s[i]!='C'&&s[i]>='A'&&s[i]<='Z') {cout<<"WA";return 0;}
		else if(s[i]=='C'&&check==true) check=false;
		else if(s[i]=='C'&&check==false) {cout<<"WA";return 0;}
	}
	if(check==true) {cout<<"WA";return 0;}
	cout<<"AC";
}


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

int main(){
  int h;
  int w;
  cin >> h >> w;
  vector<string> str;
  str.resize(h);
  int Right[h][w],Hight[h][w];
  for (int i=0;i<h;i++) cin >> str[i];
  int x=0;
  for (int i=0;i<h;i++){
    x=0;
    for (int j=0;j<w;j++){
      if (str[i][j]=='.'){
        x++;
        Right[i][j]=x;
      }else{
        x=0;
        Right[i][j]=x;
      }
    }
  }
  for (int i=0;i<w;i++){
    x=0;
    for (int j=0;j<h;j++){
      if (str[j][i]=='.'){
        x++;
        Hight[j][i]=x;
      }else{
        x=0;
        Hight[j][i]=x;
      }
    }
  }
  int y=0;
  for (int i=0;i<h;i++){
    x=0;
    for (int j=w-1;j>=0;j--){
      if (x==0){
        y=Right[i][j];
        x=1;
      }
      if (Right[i][j]==0){
        y=0;
        x=0;
      }
      Right[i][j]=y;
    }
  }
  for (int i=0;i<w;i++){
    x=0;
    for (int j=h-1;j>=0;j--){
      if (x==0){
        y=Hight[j][i];
        x=1;
      }
      if (Hight[j][i]==0){
        y=0;
        x=0;
      }
      Hight[j][i]=y;
    }
  }
  /*
  for (int i=0;i<h;i++){
    for (int j=0;j<w;j++){
      cout << Right[i][j];
    }
    cout << endl;
  }
  for (int i=0;i<h;i++){
    for (int j=0;j<w;j++){
      cout << Hight[i][j];
    }
    cout << endl;
  }
  */
  int ans=0;
  for (int i=0;i<h;i++){
    for (int j=0;j<w;j++){
      ans=max(ans,(Right[i][j]+Hight[i][j]-1));
    }
  }
  cout << ans;
}

Measured memory_bytes: 35584
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

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

int main(){
	int T; cin >> T;
    while(T--){
        ll A,B,C,D; cin >> A >> B >> C >> D;
        if(A < B){cout << "No" << endl; continue;}
        if(D < B){cout << "No" << endl; continue;}
        if(C >= B){cout << "Yes" << endl; continue;}
        ll g = GCD(B,D);
        ll ans = B-g+A%g;
        cout << (ans <= C ? "Yes" : "No") << endl;
    }
}
   


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

int main(int argc, char const *argv[]){
	
	double a,b,c,d,e,f;

	while(std::cin >> a >> b >> c >> d >> e >> f){
		double y = (a*f-c*d)/(a*e-b*d);
		double x = (c-b*y)/a;
		std::cout << std::fixed << std::setprecision(3) << x << " " << y << std::endl;
	}

	return 0;
}



Measured memory_bytes: 3180
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define X first
#define Y second
#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define DEBUG(x) cerr << #x << " = " << x << "\n"
#define UCIN ios_base::sync_with_stdio(false);cin.tie(0);

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int> pii;
typedef pair < ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vl;
typedef pair < double, double > pt;

const int N = 1e5 + 500;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 18;
const int OFF = (1 << LOG);
const double EPS = 1e-9;
const double PI = 3.1415926535;

int n;

int sum(int x){
    int sm = 0;
    while(x != 0){
        sm += x % 10;
        x /= 10;
    }
    return sm;
}

int main(){
    scanf("%d", &n);
    int sol = INF;
    for(int i = 1;i<n;i++){
        int x = i;
        int y = n - i;
        sol = min(sol, sum(x) + sum(y));
    }
    printf("%d\n", sol);
    return 0;
}


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

#define ll long long int
#define MP make_pair
#define pb push_back
#define PLL pair<ll,ll>

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

  if(n%1000 == 0)
  cout<< 0 << '\n';
  else
  {
    cout << 1000-n%1000<<'\n';
  }

}


Measured memory_bytes: 3636
#include <iostream> // cout, endl, cin
using namespace std;

int main()
{
  long long int n;
  cin >> n;
  for(long long int i = 1;i <= n;i++)
  {
    int flag = 0, tmp = i;
    for(;tmp > 0;)
    {
      if(tmp % 10 == 3) flag = 1;
      tmp /= 10;
    }
    if(i % 3 == 0||flag == 1)
    {
      cout << " " << i;
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
int main(){
	cin>>n;cout<<n*n*n<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 1000000007ll;

LL dsum(LL x)
{
  if(x<10) return x;
  else return dsum(x/10) + x%10;
}

int main(void)
{
  LL k;
  cin >> k;
  LL tmp = 1;
  LL diff = 1;
  REP(i,k) {
    cout << tmp << endl;
    if(1.0*(tmp+diff)/dsum(tmp+diff) > diff) diff*=10;
    tmp += diff;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0) return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1;  // 分母
  ll numerator = 1;    // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

int main() {
  ll X, Y;
  cin >> X >> Y;
  if (((X + Y) % 3) != 0) {
    cout << 0 << endl;
    return 0;
  }

  // (+1, +2)という移動をn回
  // (+2, +1)という移動をm回

  // 3の倍数か

  // n + 2m = X
  // 2n + m = Y

  ll ans = 0;
  for (ll n = 0; n < 1000000; n++) {
    if ((X - n) % 2 != 0) {
      continue;
    }
    if ((X - n) < 0) {
      continue;
    }
    ll m = (X - n) / 2;
    if (Y == (2 * n + m)) {
      ans += modCombination(n + m , n, MOD);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
using namespace std;
int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int d;
    if(a>b)
    {
        d=a;
        a=b;
        b=d;
    }
    if(a<c&&b>c)
        printf("Yes");
    else
        printf("No");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
  int n;
  cin >> n;
  bool flag = true;
  rep(i, n) {
    int a;
    cin >> a;
    if (a % 2 == 0) {
      if (a % 3 == 0 || a % 5 == 0) {
        flag = true;
      } else {
        flag = false;
        cout << "DENIED\n";
        return 0;
      }
    }
  }

  if (flag) {
    cout << "APPROVED\n";
  } else {

  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main()
{
	char s[11], t[11], u[11];
	int a, b;
	scanf("%s %s",&s,&t);
	scanf("%d %d",&a,&b);
	scanf("%s",&u);
	if(strcmp(u,s)==0){
		printf("%d %d\n",a-1,b);
	}
	else if(strcmp(u,t)==0){
		printf("%d %d\n",a,b-1);
	}
	
	return 0;
}

Measured memory_bytes: 2124
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pow2(x) (ll(1)<<x)
#define pb push_back
#define mp make_pair
#define w(t) int t;scanf("%d",&t);while(t--)
#define For(i,a,n) for(int i=a;i<n;i++)
#define scan(n) int n;scanf("%d", &n);
using namespace std;
const int sz = 1e3 + 5;
const int mod = 1e9 + 7;
int main()
{
    scan(n);
    ll x[n], ans = 0,sum = 0;
    For(i,0,n)
    {
        scanf("%lld", &x[i]);
        ans = (ans + x[i]  * sum) % mod;
        sum = (sum + x[i]) % mod;
    }
    cout<<ans;
}


Measured memory_bytes: 5148
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String n = sc.next();
		int k = sc.nextInt();
		sc.close();

		int[] numbers = IntStream.range(0, n.length()).map(i -> Integer.parseInt(n.substring(i, i + 1))).toArray();
		int[][] c1 = new int[n.length()][Math.max(k, n.length()) + 1];
		int[][] c2 = new int[n.length()][Math.max(k, n.length()) + 1];

		c1[0][0] = 1;
		c1[0][1] = numbers[0] - 1;
		c2[0][1] = 1;
		for (int i = 1; i < n.length(); i++) {
			for (int j = 0; j < n.length(); j++) {
				if (numbers[i] == 0) {
					c1[i][j] += c1[i - 1][j];
					c1[i][j + 1] += c1[i - 1][j] * 9;
					c2[i][j] += c2[i - 1][j];
				} else {
					c1[i][j] += c1[i - 1][j] + c2[i - 1][j];
					c1[i][j + 1] += c1[i - 1][j] * 9 + c2[i - 1][j] * (numbers[i] - 1);
					c2[i][j + 1] += c2[i - 1][j];
				}
			}
		}

		System.out.println(c1[n.length() - 1][k] + c2[n.length() - 1][k]);
	}
}


Measured memory_bytes: 26964
I=lambda:list(map(int,input().split()));n,m=I();d=[0]+[9**9]*2**n
while m:
 m-=1;a=I()[0];s=sum(2**~-c for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

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

using namespace std;
#define INFS (1LL<<28)
#define INF (1LL<<60)
#define DEKAI 1000000007
#define lp(i,n) for(int i=0;i<n;i++)
#define int long long
#define double long double

vector<int> v[500];

int che(int now){
	queue<int> q;
	q.push(now);
	int dp[500];
	lp(i,500)dp[i]=0;
	int last;
	while(!q.empty()){
		int now=q.front();
		last=now;
		q.pop();
		lp(i,v[now].size()){
			int next=v[now][i];
			if(dp[next]==1)continue;
			dp[next]=1;
			q.push(next);
		}
	}
	return last;
}

int solve(int start){
	queue<pair<int,int>> q;
	q.push({start,1});
	int dp[500];
	lp(i,500)dp[i]=0;
	dp[start]=1;
	int ans=1;
	while(!q.empty()){
		int now=q.front().first;
		int num=q.front().second;
		q.pop();
		lp(i,v[now].size()){
			int next=v[now][i];
			if(dp[next]!=0){
				if(abs(dp[next]-num)!=1){
					return -1;
				}
				continue;
			}
			dp[next]=num+1;
			q.push({next,num+1});
			ans=num+1;
		}
	}
	return ans;
}

signed main(){
	int n;
	cin>>n;
	lp(i,n){
		string s;
		cin>>s;
		for(int j=i+1;j<s.size();j++){
			if(s[j]=='1'){
				v[i].push_back(j);
				v[j].push_back(i);
			}
		}
	}
	int ans=-1;
	lp(i,n){
		ans=max(ans,solve(i));
	}

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


Measured memory_bytes: 640
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;
use std::ops::Bound::*;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);

    let mut uft = UnionFindTree::new(n);
    for i in 0..m {
        let v = read_vec::<usize>();
        let (a, b) = (v[0] - 1, v[1] - 1);
        uft.unite(a, b);
    }

    let mut ans = 0;
    for i in 0..n {
        if i == uft.find(i) {
            ans += 1;
        }
    }
    ans -= 1;
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

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

#[derive(Debug, Clone)]
struct UnionFindTree {
    parent: Vec<isize>,
    size: Vec<usize>,
    height: Vec<u64>,
}

impl UnionFindTree {
    fn new(n: usize) -> UnionFindTree {
        UnionFindTree {
            parent: vec![-1; n],
            size: vec![1usize; n],
            height: vec![0u64; n],
        }
    }

    fn find(&mut self, index: usize) -> usize {
        if self.parent[index] == -1 {
            return index;
        }
        let idx = self.parent[index] as usize;
        let ret = self.find(idx);
        self.parent[index] = ret as isize;
        ret
    }

    fn same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    fn get_size(&mut self, x: usize) -> usize {
        let idx = self.find(x);
        self.size[idx]
    }

    fn unite(&mut self, index0: usize, index1: usize) -> bool {
        let a = self.find(index0);
        let b = self.find(index1);
        if a == b {
            false
        } else {
            if self.height[a] > self.height[b] {
                self.parent[b] = a as isize;
                self.size[a] += self.size[b];
            } else if self.height[a] < self.height[b] {
                self.parent[a] = b as isize;
                self.size[b] += self.size[a];
            } else {
                self.parent[b] = a as isize;
                self.size[a] += self.size[b];
                self.height[a] += 1;
            }
            true
        }
    }
}


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

using namespace std; 

#define pb push_back
#define fi first
#define se second
#define all(vec) vec.begin(),vec.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define fp(i,a,b,p) for(int i=a;i<b;i+=p)
#define SZ(x) (int)x.size()

typedef  vector<string> vs;
typedef  vector<int> vi;
typedef  vector<long long> vl;	


int main(){
	
	int n;
	
	
	cin >> n; 
	
	vi v(n); 
	
	f(i,0,n){
		cin >> v[i];
	}
	
	vi even(100005);
	vi odd (100005);
	
	int ansODD = 0;
	int ansEven = 0;
	int secondODD = 0;
	int secondEven = 0;
	int idx = 0 , idy = 0;
	f(i,0,n){
		if(i%2==0){
			even[v[i]]++;
			if(ansEven<=even[v[i]]){
				ansEven = even[v[i]];
				idx = v[i];
			}
		}else{
			odd[v[i]]++;
			if(ansODD<=odd[v[i]]){
				ansODD = odd[v[i]];
				idy = v[i];
			}
		}
	}
	
	f(i,0,n){
		if(i%2==0){
			if(even[v[i]]<= ansEven && idx!=v[i] && secondEven <=even[v[i]]){
				secondEven = even[v[i]];
			}
		}else{
			if(odd[v[i]]<= ansODD && idy!=v[i] && secondODD <=odd[v[i]]){
				secondODD = odd[v[i]];
			}
		}
	}
	
	int result = 0;
	
	if(idx == idy){
		if(ansEven>ansODD){
			result = n - ansEven - secondODD;
		}else{
			if(ansODD > ansEven){
				result = n - secondEven - ansODD;
			}else{
				result = n  - ansEven - max(secondEven,secondODD);
			}
		}
	}else{
		result =  n - ansEven - ansODD;
	}
	
	cout <<  result << endl;
	
	

    return 0;
}


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

int32_t main() {
  int x, y;
  scanf("%d%d", &x, &y);

  int all_crane = x<<1;
  int all_turtle = x<<2;

  puts(((y&1) || y < all_crane || y > all_turtle) ? "No" : "Yes");

  return 0;
}


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

typedef long long ll;

const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int mypow(mint p, int n){
    mint res = 1;
    while (n>0){
        if (n%2==0){
            p *= p;
            n /= 2;
        } else {
            res *= p;
            n--;
        }
    }
    return res.x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i=0;i<N;i++) cin >> A[i];
    sort(A.begin(),A.end());
    if (N%2==1) {
        if (A[0] != 0) {
            cout << 0 << "\n";
            return 0;
        }
        for (int i=1;i<N;i++){
            if (A[i] != (i+1)/2*2) {
                cout << 0 << "\n";
                return 0;
            }
        }
        cout << mypow(mint(2),(N-1)/2) << "\n";
        return 0;
    } else {
        for (int i=0;i<N;i++){
            if (A[i] != i/2*2+1) {
                cout << 0 << "\n";
                return 0;
            }
        }
        cout << mypow(mint(2),N/2) << "\n";
        return 0;
    }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int a,b,c,k;
   cin>>a>>b>>c>>k;
   while(k&&a>=b)
   {
     k--;
     b*=2;
   }
    while(k&&b>=c)
   {
     k--;
     c*=2;
   }
  if(a<b&&b<c)
    cout<<"Yes";
  else
     cout<<"No";
  return 0;
}


Measured memory_bytes: 3608
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 3010;

double dp[N];

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif

  int n;
  scanf("%d", &n);
  dp[0] = 1;
  for (int i = 1; i <= n; ++i) {
    double p;
    scanf("%lf", &p);
    for (int j = i; j; --j)
      dp[j] = dp[j] * (1 - p) + dp[j - 1] * p;
    dp[0] *= 1 - p;
  }
  printf("%.10lf\n", accumulate(dp + (n + 1) / 2, dp + n + 1, 0.));

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static final double EPS=0.00001;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		while(true){
			int n=sc.nextInt();
			if(n==0) break;
			long stair[]=new long[n+1];
			stair[0]=1;
			for(int i=1;i<=n;i++){
				int sum=0;
				for(int j=1;j<=3;j++){
					if(0<=i-j){
						sum+=stair[i-j];
					}
				}
				stair[i]=sum;
			}
			
//			for(int i=0;i<=n;i++){
//				System.out.println(stair[i]);
//			}
			
			System.out.println((long)Math.ceil(Math.ceil(stair[n]/10)/365+EPS));
		}

	}

}

Measured memory_bytes: 17200
#include <iostream>
using namespace std;
main() {
	int n,i,sum=0;
	cin>>n;
	int x[n-1], y[n-1],s[n-1];
	
	for(i=0; i<n; i++) {
		cin>>x[i];
	}
	
	for(i=0; i<n; i++) {
		cin>>y[i];
	}
	
	for(i=0; i<n; i++) {
		s[i]=x[i]-y[i];
	}
	
	for(i=0; i<n; i++) {
		if(s[i]>0) sum+=s[i];
	}
	
	cout<<sum;
}

Measured memory_bytes: 256
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a,int b){return a*b/gcd(a,b);}

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

signed f(int num){
    if(num%2==0)return num/2;
    else return num*3+1;
}

void run(){
    int s;
    cin >> s;
    int num=4;
    if(s==2)
    {
        cout << 4  << endl;
        return;
    }
    if(s==1)
    {
        cout << 4 << endl;
        return;
    }
    while(s!=4)
    {
        ++num;
        s=f(s);
    }
    cout << num << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<P> v(m);
    rep(i, m)
    {
        cin >> v[i].second >> v[i].first;
    }
    sort(v.begin(), v.end());
    int last = 0;
    int ans = 0;
    for (auto p : v)
    {
        if (p.second > last)
        {
            last = p.first - 1;
            ans++;
        }
    }
    cout << ans << endl;
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int h, w;
vector<string> c;

int f[12];
int used[12];

bool same(int i, int j) {
    inc(k, 0, h){
        if(c[f[k]][i] != c[f[h-k-1]][j]) return false;
    }
    return true;
}

bool dfs2(int cnt, int flag) {
    if(cnt == w){
        return true;
    }

    bool res = false;

    inc(i, 0, w){
        if(used[i]) continue;
        inc(j, i+1, w){
            if(used[j]) continue;
            if(same(i, j)){
                used[i] = 1;
                used[j] = 1;
                return dfs2(cnt+2, flag);
            }
        }
        if(flag == 0 && same(i, i)){
            used[i] = 1;
            res |= dfs2(cnt+1, flag+1);
            used[i] = 0;
        }
        break;
    }

    return res;
}

bool dfs1(int idx, int bit) {
    bool res = false;
    int cnt = 0;
    inc(i, 0, h){
        if((bit & (1 << i)) != 0) cnt++;
    }

    if(cnt == h){
        inc(i, 0, w){
            used[i] = 0;
        }
        return dfs2(0, 0);
    }

    if(cnt == 0 && h%2 == 1){
        inc(i, 0, h){
            f[h/2] = i;
            res |= dfs1(0, bit | (1 << i));
            f[h/2] = -1;
        }
    }else{
        inc(i, 0, h){
            if((bit & (1 << i)) != 0) continue;

            inc(j, i+1, h){
                if((bit & (1 << j)) != 0) continue;

                f[idx] = i;
                f[h-idx-1] = j;
                res |= dfs1(idx+1, bit | (1 << i) | (1 << j));
                f[idx] = -1;
                f[h-idx-1] = -1;
            }
            break;
        }
    }

    return res;
}

int main() {
    cin >> h >> w;
    inc(i, 0, h){
        string s;cin >> s;
        c.pb(s);
    }

    inc(i, 0, h) f[i] = -1;

    cout << (dfs1(0, 0) ? "YES" : "NO") << endl;

    return 0;
}


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


using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    char ch;
    cin>>ch;
    int x=(int)ch;
    if(x>=65 && x<=90)
    cout<<"A"<<endl;
    else
    cout<<"a"<<endl;
  
  return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n) for(int i= 0; i <(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main()
{
    int n;
    cin >>n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    sort(a.rbegin(),a.rend());
    ll ans =0;
    int t = n-1;
    rep(i,n){
        int lim =2;
        if(i == 0 )lim=1;
        rep(j,lim){
        if(t > 0){
            ans += a[i];
            t--;
            }
    }}

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

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

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

int main() {
  int num,point;
  long long tmp1, tmp2;
  cin >> num >> point;
  vector<pair<long long, long long>> pN(num);
  vector<pair<long long, long long>> pP(point);
  vector<long long> vec(num,0);
  
  for(int i = 0; i < num; i++){
    cin >> tmp1 >> tmp2;
    pN.at(i) = make_pair(tmp1, tmp2);
  }
  
  for(int i = 0; i < point; i++){
    cin >> tmp1 >> tmp2;
    pP.at(i) = make_pair(tmp1, tmp2);
  }
  
  for(int i = 0; i < num; i++){
    long long Min = 9999999999;
    for(int j = 0; j < point; j++){
      long long x1,y1,x2,y2;
      tie(x1, y1) = pN.at(i);
      tie(x2, y2) = pP.at(j);

      tmp1 = abs(x1 - x2);
      tmp2 = abs(y1 - y2);
      //Min = max(Min, tmp1 + tmp2);
      if(chkMin(Min, tmp1 + tmp2) == true){
        vec.at(i) = j+1;
      }
    }
  }
  
  for(int i = 0; i < num; i++){
    cout << vec.at(i) << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int N;
      cin >> N;
      int K;
      cin >> K;
      int x;
      int min=0;
      
      // ここにプログラムを追記
      for(int i=0;i<N;i++){
        cin >> x;
        if( K-x > x){
          min+=2*x;
        }else{
          min+=2*(K-x);
        }
      }
      cout << min << endl;
      
    }

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define RI(a) scanf("%d",&a)
#define RII(a,b) scanf("%d%d",&a,&b)
#define RIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define F first
#define S second
#define REP(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
//}}}
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;

int main()
{
	string s;
	cin>>s;
	if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I') puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

template <class T> void vecout(T V) {
    auto t = V.begin();
    while(t != V.end()) {
        cout << *t++;
        if(t != V.end()) cout << " ";
    }
    cout << endl;
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q, b, e;
    cin >> n;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    cin >> q;
    rep(i, q) {
        cin >> b >> e;
        reverse(v.begin() + b, v.begin() + e);
    }
    vecout(v);
}



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

int main(){
  int ans=0;
  string S;
  cin>>S;
  if(S[0]=='+'){
    ans++;
  }
  if(S[0]=='-'){
    ans--;
  }
  if(S[1]=='+'){
    ans++;
  } 
  if(S[1]=='-'){
    ans--;
  }
  if(S[2]=='+'){
    ans++;
  }
  if(S[2]=='-'){
    ans--;
  }
  if(S[3]=='+'){
    ans++;
  }
  if(S[3]=='-'){
    ans--;
  }
  cout<<ans<<endl;
}
  
  
  
  
  


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	ll A[200001],B[200001];
	vpll BA;
	scan(N);
	rep(i,N){
		scan(A[i]>>B[i]);
		BA.push_back({B[i],A[i]});
	}
	sort(BA.begin(),BA.end());
	ll time=0;
	int flag=1;
	rep(i,N){
		time+=BA[i].second;
		if(time>BA[i].first) flag=0;
	}
	if(flag) prin("Yes");
	else prin("No");
	return 0;
}


Measured memory_bytes: 9200
import java.util.*;

import java.lang.*;

import java.math.*;



public class Main {

	Scanner sc = new Scanner(System.in);



	void run() {

		for (;;) {

			String buffer = sc.nextLine();

			int size = Integer.valueOf(buffer);

			if (size == 0)

				break;

			boolean[][] map = new boolean[size + 1][size + 1];

			for (int i = 0; i < size; i++) {

				buffer = sc.nextLine();

				for (int j = 0; j < size; j++) {

					map[i + 1][j + 1] = buffer.charAt(j) == '.';

				}

			}

			int[][] sq = new int[size+1][size+1];

			int max = 0;

			for (int i = 1; i < size + 1; i++) {

				for (int j = 1; j < size + 1; j++) {

					if (map[i][j]) {

						if (map[i - 1][j] && map[i - 1][j - 1] && map[i][j - 1]) {

							sq[i][j] = Math.min(Math.min(sq[i - 1][j],sq[i - 1][j - 1] ), sq[i][j - 1])+1;

						} else {

							sq[i][j] = 1;

						}

					}

					if(max < sq[i][j]) max = sq[i][j];

				}

			}

			System.out.println(max);

		}



	}



	public static void main(String[] args) {

		Main m = new Main();

		m.run();

	}

}

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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(a==b&&b==c){
    cout << 1 << endl;
  }
  else if(a!=b&&b!=c&&c!=a){
    cout << 3 << endl;
  }else{
    cout << 2 << endl;
  }
}


Measured memory_bytes: 256
open Batteries
let () =
  let a,b,c = Scanf.scanf "%s %s %s " (fun a b c -> a,b,c) in

  let a = String.uppercase_ascii (String.sub a 0 1) in
  let b = String.uppercase_ascii (String.sub b 0 1) in
  let c = String.uppercase_ascii (String.sub c 0 1) in

  Printf.printf "%s\n" (a ^ b ^ c)


Measured memory_bytes: 1536
#include<stdio.h>
int main(){
  int n,a,b,t[10000];
  int i,j,k,l,p,m;
  double c,max;
  //unsigned long long m;
  scanf("%d",&n);
  scanf("%d %d",&a,&b);
  scanf("%d",&k);
  for(i=0;i<n;i++){
    scanf("%d",&t[i]);
  }
  for(i=0;i<n;i++){
    for(j=1;i+j<n;j++){
      if(t[j-1]<t[j]){
	m=t[j];
	t[j]=t[j-1];
	t[j-1]=m;
      }
    }
  }
  max=0.0;
  l=i;
  c=k;
  p=a;
  for(j=0;j<n;j++){
    c+=t[j];
    p+=b;
    if(max>c/p)break;
    max=c/p;
  }
  printf("%d\n",(int)max);
  return 0;
}
      

Measured memory_bytes: 604
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define EB emplace_back
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

vector<vector<int>> v;
const int N = 2e5;
int dis[N];
int par[N];
int n,m;
            
void solve(int s)
{
	for(int i = 0; i < N; i++) dis[i] = -1, par[i] = -1;
	queue< int >q;
	q.push(s);
	dis[s]=0;
	while(!q.empty())
	{
		int cn=q.front();
		q.pop();

		for(auto it:v[cn])
		{
			if(dis[it]==-1)
			{
				par[it]=cn;
				dis[it]=dis[cn]+1;
				q.push(it);
			}
		}
	}
}

 
int32_t main() {
	IOS;
	
	cin >> n >> m;
	v.resize(n + 1);
	for(int i = 0;i < m; i++)
	{
	int a,b;
	cin >> a >> b;
	v[a].EB(b);
	v[b].EB(a);
	}
	solve(1);
	bool ok = true;
	for(int i = 2; i <= n; i++)
	{
		if(dis[i]<0)
		ok=0;

	}
	if(ok)
	{
		cout<<"Yes"<<endl;
		for(int i = 2; i <= n; i++)
		cout << par[i] <<endl;
	}
	else cout << "No";
	return 0;
}


Measured memory_bytes: 15180
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;

/**
 * Art Exhibition
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		int N = parseInt(br.readLine());

		long[][] AB = new long[N][2];

		for (int i = 0; i < N; i++) {
			line = br.readLine();
			AB[i][0] = parseLong(line.substring(0, line.indexOf(' ')));
			AB[i][1] = parseLong(line.substring(line.indexOf(' ') + 1));
		}

		Arrays.sort(AB, new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				return Long.compare(o1[0], o2[0]);
			}
		});

		long ans, acc, min;
		ans = acc = min = 0;

		for (int i = 0; i < N; i++) {
			min = Math.min(min, acc - AB[i][0]);
			acc += AB[i][1];
			ans = Math.max(ans, acc - AB[i][0] - min);
		}

		System.out.println(ans);
	}
}


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

int main(void) {
unsigned int N;
unsigned long int T,a,b;
unsigned long int t[200000];
cin >> N >> T;
for (int i=0; i < N; i++) {
cin >> t[i];
}

b=0;
for (int i =0; i < N-1; i++) {
a = t[i] + T;
if (a < t[i+1]) {
b = b + T;
} else {
b = b + t[i+1] - t[i];
}
}
b = b + T;
cout << b << endl;
}

Measured memory_bytes: 1792
a,b,c = gets.split.map(&:to_i)

i = 1

cand = []

while true do
  toc = a * i % b
  if cand.include? toc
    puts 'NO'
    exit 0
  end

  if toc == c
    puts 'YES'
    exit 0
  else
    cand << toc
  end
  i += 1
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef set<ll> sl;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    ll n, k;
    cin >> n >> k;
    vl a(n+1);
    rep(i,1,n+1) {
        cin >> a[i];
    }
    vl b(n+1);
    rep(i,1,n+1) {
        b[i] = max(a[i],0LL);
        b[i] += b[i-1];
    }
    /*rep(i,1,n+1) {
        cout << b[i] << " ";
    }
    cout << endl;*/
    vl c(n+1);
    rep(i,1,k+1) {
        c[1] += a[i];
    }
    rep(i,2,n-k+2) {
        c[i] = c[i-1] - a[i-1] + a[i+k-1];
    }

    ll ret = 0;
    rep(i,1,n-k+2) {
        ll locret = b[i-1] + b[n] - b[i+k-1] + max(c[i],0LL);
        ret = max(ret, locret);
    }
    cout << ret << '\n';
    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N; cin >> N;
	long long A[3 * N];
	for (int i = 0; i < 3 * N; i++) {
		cin >> A[i];
	}
	long long ans = 0;
	sort(A, A + 3 * N);
	for (int i = 2; i <=2*N; i += 2) {
		ans += A[3 * N - i];
	}
	cout << ans << endl;
	return 0;
}

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

int a[300000];
int main(){
	int n;cin>>n;
	rep(i,n)scanf("%d",&a[i]);
	ll ans=0;
	ll cur=0;
	rep(i,n){
		if(cur>a[i]){
			ans+=cur-a[i];
		}
		else cur=a[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4496
N,Q=map(int,input().split())
S=input()

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])


Measured memory_bytes: 51288
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define fi first
#define se second

main(){
    string s;
    cin>>s;
    r(i,3){
        if(s[i]=='1')s[i]='9';
        else if(s[i]=='9')s[i]='1';
    }
    cout<<s<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <bitset>
#include <tuple>
#include <stack>
#include <utility>

using namespace std;

int main(){
    int N, A;
    cin >> N >> A;
    int ans = N*N - A;
    cout << ans << endl;
    return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> C(N);
    for(int i=0; i<N; i++){
        cin >> C[i];
        C[i]--;
    }
    vector<int> edges[200000];
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    vector<vector<int>> res(N);

    vector<int> cnt(N);
    vector<map<int, int>> dp(N);
    auto dfs = [&](auto&& dfs, int i, int p)->void{
        for(int j : edges[i]) if(j != p){
            dfs(dfs, j, i);
            cnt[i] += cnt[j];

            int c = cnt[j];
            if(dp[j].count(C[i])) c -= dp[j][C[i]];
            res[C[i]].push_back(c);
            
            if(dp[i].size() < dp[j].size()) swap(dp[i], dp[j]);
            for(auto& p : dp[j]) dp[i][p.first] += p.second;
        }
        cnt[i]++;
        dp[i][C[i]] = cnt[i];
    };
    dfs(dfs, 0, -1);
    for(int i=0; i<N; i++) res[i].push_back(N - dp[0][i]);
    
    int64_t all = int64_t(N)*(N+1)/2;
    vector<int64_t> ans(N, all);
    for(int i=0; i<N; i++) for(int64_t a : res[i]) ans[i] -= a*(a+1)/2;
    
    for(auto a : ans) cout << a << endl;
    return 0;
}


Measured memory_bytes: 80376
#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
using namespace std;
int main(void)
{
	ll n, i, t1, t2, t3;
	cin>>n;
	ll dp[n+1][3];
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	for(i=1; i<=n; i++)
	{
		cin>>t1>>t2>>t3;
		dp[i][0] = t1 + max(dp[i-1][1], dp[i-1][2]);
		dp[i][1] = t2 + max(dp[i-1][0], dp[i-1][2]);
		dp[i][2] = t3 + max(dp[i-1][0], dp[i-1][1]);
	}
	cout<<max(dp[n][0], max(dp[n][1], dp[n][2]))<<"\n";
}	

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

using i64 = int64_t;
i64 INF = 1ll << 60;

inline void chmin(i64 &a, i64 b){
  if(a > b)
    a = b;
}

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> h(110000);
  for(int i = 0; i < n; i++)
    cin >> h[i];
  
  vector<i64> cost(110000);
  for(int i = 0; i < cost.size(); i++)
    cost[i] = INF;
  cost[0] = 0;
  
  for(int i = 0; i < n; i++){
    for(int j = 1; j <= k; j++)
      chmin(cost[i+j], cost[i]+abs(h[i]-h[i+j]));
  }
  
  cout << cost[n-1] << endl;
  
  return 0;
  
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
#define REP(i,x,n) for(int i=x; i<n; i++)
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(), x.end()

int main(){
  int n;
  cin >> n;
  vd v(n);
  rep(i,n)  cin >> v[i];

  sort(all(v));
  double ans= v[0];

  REP(i,1,n){
    ans= (ans+v[i])/2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<long long int,long long int>,null_type,less<pair<long long int,long long int> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int num=(int)1e6+1;

void go()
{
    long long int a,b,c,k;
    cin>>a>>b>>c>>k;
    long long int ans=0;
    if(k <= a)
    {
        ans+=k;
        cout<<ans;
        return ;
    }
    else if(k > a)
    {
        ans+=a;
        k-=a;
        if(k <= b)
        {
            cout<<ans;
            return ;
        }
        else
        {
            k-=b;
            if(k <= c)
            {
                cout<<ans-k;
                return ;
            }
            else
            {
                cout<<ans-c;
                return;
            }
        }
    }
}
int main()
{
    FIO;
    go();
    return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
#define debug(x) cerr << x << endl
#define Complex complex<double>
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

/*
テストケース全てに目を通す
テストケースが2個以下だったらなんかある
N最小のコーナーケースがないか調べる
制約をしっかりと確認する（1からNまでの順列、全て異なる値などの制約も含め）
制約のn*mとn,mを読み違えない
操作の逆順を考える
オーバーフローしないか確かめる
Codeforcesではscanfを使う
modの引き算には+modをする
エラー出力は消す
エラー出力を消せ！！！！！
数値の区切り位置を誤読しない
cout << fixed;
cout << setprecision(n) << ans;
 */

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> p(n);
    vector<int> q(n);
    rep(i,n)v[i]=i+1;
    rep(i,n)cin >> p[i];
    rep(i,n)cin >> q[i];
    int cnt=0;
    int a,b;
    do{
        cnt++;
        if(v==p)a=cnt;
        if(v==q)b=cnt;
    }while(next_permutation(all(v)));
    cout << abs(a-b);
}

/*
*/



Measured memory_bytes: 256