akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Math;

namespace AtCodeeeer
{
    class AtCOOOOOOOOOOOder
    {
        static void Main(string[] args)
        {
            int[] s = ReadLine().Split(' ').Select(int.Parse).ToArray();
            int R = s[0];
            int G = s[1];
            int B = s[2];
            int N = s[3];

            int ans = 0;int r = R; int g = G;
            for (int i = 0; i <= N / R; i++)
            {
                r = R * i;
                for (int j = 0; j <= N / G; j++)
                {
                    g = G * j;
                    if (0<= (N - (r + g)) && (N - (r + g)) % B == 0)
                    {
                        ans++;
                    }
                }
            }
            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <vector>
#include <map>
#include<cstdio>
#include<functional>
#include <bitset>
#include <iomanip>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define ll long long
using namespace std;
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;

int main()
{
	string s;
	ll k;
	cin >> s >> k;
	ll tmp = 0;
	vector<ll> l;
	rep(i, s.size()) {
		ll num = s[i] - '0';
		l.push_back(num);
	}
	int ans = 0;
	rep(i, s.size()) {
		if (l[i] != 1) {
			ans = l[i];
			break;
		}
		if (i + 1 == k) {
			ans = 1;
			break;
		}
	}
	cout << ans << endl;
	//cout << fixed << setprecision(10) << ans << endl;
	system("pause");
}



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

int main(){
    int a,b,c,temp;
    cin >> a >> b >>c ;
    if(a>b){
        temp=a;
        a=b;
        b=temp;
    }
     if(b>c){
        temp=b;
        b=c;
        c=temp;
    }
     if(a>b){
        temp=a;
        a=b;
        b=temp;
    }
    cout << a << " " << b << " " << c << endl;
    
    return 0;
}


Measured memory_bytes: 3084
# coding: utf-8
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

def printd(str)
  print str if $debugFlag
end

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if false
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

xx = inputs[0][1]
lst = inputs[1]

ans = 0
for i in 0..lst.size-2
  if lst[i] + lst[i+1] > xx
    delta = (lst[i] + lst[i+1] - xx)
    ans += delta
    lst[i+1] -= delta
    if lst[i+1] < 0
      lst[i] += lst[i+1]
      lst[i+1] = 0
    end
  end
end

puts ans



Measured memory_bytes: 9620
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int lld;

const lld mod = 1e9+7;
const lld INF = 1e9;
//const lld MAXN = 1e9;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	vector<int> cnt(n+1);

	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		if (a[i]<= n)
		{
			cnt[a[i]]++;
		}else{
			ans++;
		}
	}

	for(int j = 1; j <= n; j++)
	{
		if (cnt[j]> j)
		{
			ans += (cnt[j]-j);
		}else if(cnt[j]<j)
		{
			ans += cnt[j];
		}
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 1024
S = input()
T = input()

X = {}
Y = {}

for i in range(len(S)):
  if not S[i] in X:
    X[S[i]] = T[i]
  elif X[S[i]] == T[i]:
    pass
  else:
    print("No")
    exit(0)

  if not T[i] in Y:
    Y[T[i]] = S[i]
  elif Y[T[i]] == S[i]:
    pass
  else:
    print("No")
    exit(0)

print("Yes")

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

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

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

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

    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for (ll i=2;i<n;i++) {
        dp[i] = min(abs(h[i]-h[i-1])+dp[i-1],abs(h[i]-h[i-2])+dp[i-2]);
    }

    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

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

void solve() {
    int S,W;
    cin >> S >> W;
    auto ans = (W >= S) ? "unsafe" : "safe";
    cout << ans << endl;
}

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


Measured memory_bytes: 3636
a, b = map(int, input().split())

if a & 1 == 0 and (b-a+1)%2==0:
    ans = ((b-a+1)//2)%2
elif a & 1 == 0 and (b-a+1)%2==1:
    ans = ((b-a+1)//2)%2 ^ b
elif a & 1 == 1 and (b-a)%2==0:
    ans = ((b-a)//2)%2 ^ a
else:
    ans = ((b-a)//2)%2 ^ a ^ b
print(ans)
    

Measured memory_bytes: 3060
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 3005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,dp[li][li][4];
int cev;
string s;
vector<int> v;

inline int f(int l,int r,int kim){
	int cevv=-inf;
	if(kim==1)cevv=inf;
	if(l>r)return 0;
	if(~dp[l][r][kim])return dp[l][r][kim];
	if(kim==0){
		cevv=max(cevv,f(l+1,r,!kim)+a[l]);
		cevv=max(cevv,f(l,r-1,!kim)+a[r]);
	}
	if(kim==1){
		cevv=min(cevv,f(l+1,r,!kim)-a[l]);
		cevv=min(cevv,f(l,r-1,!kim)-a[r]);
	}
	return dp[l][r][kim]=cevv;
}

main(void){
	memset(dp,-1,sizeof(dp));
	scanf("%lld",&n);
	FOR{
		scanf("%lld",&a[i]);
	}
	printf("%lld\n",f(1,n,0));
	return 0;
}



Measured memory_bytes: 286156
N, M = [int(i) for i in input().split()]
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(i)-1 for i in input().split()]
    G[a].append(b)
    G[b].append(a)

prev = [-1] * N

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        prev[w] = v
        que.append(w)

print("Yes")
print(*[prev[i]+1 for i in range(1, N)], sep='\n')


Measured memory_bytes: 39400
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) sort((a).rbegin(),(a).rend());
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl;
#define printD(a) cout << setprecision(10) << ans << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<int>& a,int n);

int n,m;


struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank; // ランク

    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n); rank.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};


int judge(string a,int piv,string b){
	REP(i,b.size()){
		if(a[piv+i] != b[i]){
			return 1;
		}
	}
	return 0;
}


/*
eraser
erasee
erased
dreamdream
dreamerdream
dreamererase
dreamerase
 */

signed main(){
	string s;
	cin >> s;
	s += 'x';
	int piv = 0;
	bool ans = true;
	while(piv<s.size()){
		if(s[piv] == 'd'){
			string b = "dream";
			if(judge(s,piv,b) == 0){
				piv += 5;
				string c = "er";
				if(judge(s,piv,c) == 0){
					c = "era";
					if(judge(s,piv,c) != 0){
						piv += 2;
					}
				}
			}
			else{
				ans = false;
				break;
			}
		}
		else if(s[piv] == 'e'){
			string b = "erase";
			if(judge(s,piv,b) == 0){
				piv += 5;
				if(s[piv] == 'r') piv++;
			}
			else{
				ans = false;
				break;
			}
		}
		else if(s[piv] == 'x'){
			break;
		}
		else{
			ans = false;
			break;
		}
	}
	(ans)? cout << "YES" : cout << "NO";

    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<int>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INT_INF = 2147483647;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef pair<int,int> P;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};
//UnionFind Uni(N);
//Uni.connect;

int deg[100005];
vector<int> to[100005];

int main(){
  int n,m,k;
  cin >> n >> m >> k;
  UnionFind Uni(n);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--,b--;
    deg[a]++;
    deg[b]++;
    Uni.connect(a,b);
  }
  rep(i,k){
    int c,d;
    cin >> c >> d;
    c--,d--;
    to[c].push_back(d);
    to[d].push_back(c);
  }
  rep(i,n){
    int ans = Uni.size(i) - deg[i] - 1;
    for(int u :to[i]){
      if(Uni.root(u)==Uni.root(i))ans--;
    }
    cout << ans << ' ';
  }
  cout << endl;
}


Measured memory_bytes: 6784
N, M = map(int, input().split())
ans = [0] * N
ans_flag = [0] * N  # s桁目に条件がきたら1

for _ in range(M):
    s, c = map(int, input().split())
    if N != 1 and s == 1 and c == 0:  # 一番左が1の時点でN(>=2)桁がありえない
        print(-1)
        exit()
    elif ans_flag[s-1] == 1 and ans[s-1] != c:
        print(-1)
        exit()
    else:
        ans[s-1] = c
        ans_flag[s-1] = 1

if N != 1 and ans[0] == 0:  # 一番左が0の場合は1にすれば最小になる
    ans[0] = 1

print(int("".join(map(str, ans))))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,K;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
ll dp[305][305][305];//l～rでK回変更の最長

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>s>>K;
    rrrep(i,Size(s)-1,0){
        rrep(j,i,Size(s)){
            rep(k,K+1){
                if(i==j){
                    dp[i][j][k]=1;
                }
                else if(i+1==j){
                    if(s[i]==s[j]){
                        dp[i][j][k]=2;
                    }
                    else if(k>0){
                        dp[i][j][k]=2;
                    }
                    else{
                        dp[i][j][k]=1;
                    }
                }
                else{
                    dp[i][j][k]=max(dp[i+1][j][k],dp[i][j-1][k]);
                    if(s[i]==s[j]){
                        dp[i][j][k]=max(dp[i+1][j-1][k]+2,dp[i][j][k]);
                    }
                    if(k>0){
                        dp[i][j][k]=max(dp[i+1][j-1][k-1]+2,dp[i][j][k]);
                    }
                }
            }
        }
    }
    Cout(dp[0][Size(s)-1][K]);
    return 0;
}


Measured memory_bytes: 219392
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

template<typename T,typename F,typename G,typename H>
class DAG{
  private:
    int v;
    std::vector<std::vector<std::pair<int,T>>> to;
    std::vector<int> rank;
    std::vector<T> dp;
  public:
    DAG(int v,const T &x=T(0)):v(v){
        to.resize(v);
        rank.resize(v);
        dp.resize(v,x);
        std::iota(rank.begin(),rank.end(),0);
    }
    void add(int a,int b,const T &c=0){
        to[a].push_back(std::make_pair(b,c));
        if(rank[a]>rank[b]) std::swap(rank[a],rank[b]);
    }
    void set(int i,const T &x){
        dp[i]=x;
    }
    std::vector<T> calc(F f,H h=[](ll a,T b){return b;},G g = std::plus<T>()){
        std::vector<int> vertex(v);
        std::vector<T> tmp=dp;
        for(int i=0;i<v;++i) vertex[rank[i]]=i;
        for(int i=0;i<v;++i){
            ll sz=to[vertex[i]].size();
            for(const auto &e:to[vertex[i]]){
                tmp[e.first]=f(tmp[e.first],g(h(sz,tmp[i]),e.second));
            }
        }
        return tmp;
    }
};

int main(){
    int N,K;
    cin>>N>>K;
    vector<int> h(N);
    REP(i, N) cin >> h[i];
    auto f=[](int a,int b){return min(a,b);};
    auto g=[](int a,int b){return a+b;};
    auto H=[](int a,int b){return b;};
    DAG<int,decltype(f),decltype(g),decltype(H)> D(N,1e9);
    REP(i,N) REP(j,K){
        if(i+j+1<N) D.add(i,i+j+1,llabs(h[i+j+1]-h[i]));
    }
    D.set(0,0);
    cout<<D.calc(f,H,g)[N-1]<<endl;
}


Measured memory_bytes: 105984
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N,X=map(int,readline().split())
    L=list(map(int,readline().split()))

    S=[0]*(N+1)
    for i in range(1,N+1):
        S[i]+=S[i-1]+L[i-1]
    res=0
    for i in range(N+1):
        if S[i]<=X:
            res+=1
        else:
            break
    print(res)
if __name__=="__main__":
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

ll gcd(ll n, ll m){
  if(n%m == 0) return m;
  return gcd(m, n%m);
}

ll lcm(ll n, ll m){
  return n * m / gcd(n, m);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  int ans = 1;
  REP(i, n){
    int tmp; cin >> tmp;
    ans = lcm(tmp, ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const int maxn=55;
int n,x,d,p[maxn],sz[maxn];LL m[maxn];

vector<LL> vs[maxn];
vector<pair<pair<int,LL>,int> >all;
LL dp[maxn*maxn*maxn];
bool cmp(pair<pair<int,LL>,int> a,pair<pair<int,LL>,int> b){return (a.ff.ff*b.ff.ss)>(a.ff.ss*b.ff.ff);}

int main()
{
	scanf("%d%d%d%lld",&n,&x,&d,m+1);
	for(int i=2;i<=n;i++)scanf("%lld%d",m+i,p+i);
	
	for(int i=1;i<=n;i++)sz[i]=1;
	for(int i=n;i>=2;i--)
	{
		sz[p[i]]+=sz[i];
		m[p[i]]+=m[i];
	}
	
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		int ub=min(d,50);if(i==1)ub=50;
		if(i==1)all.pb(mp(mp(sz[i],m[i]),inf));
		else if(d>ub)all.pb(mp(mp(sz[i],m[i]),d-ub));
		for(int j=0;j<ub;j++)
		{
			vs[sz[i]].pb(m[i]);
			sum+=sz[i];
		}
	}
	dp[0]=0;for(int i=1;i<=sum+1;i++)dp[i]=Linf;
	for(int i=1;i<=n;i++)if((int)vs[i].size())
	{
		sort(vs[i].begin(),vs[i].end());
		for(int j=sum;j>=0;j--)if(dp[j]!=Linf)
		{
			LL cur=dp[j];
			for(int k=0;k<(int)vs[i].size();k++)
			{
				cur+=vs[i][k];
				dp[j+(k+1)*i]=min(dp[j+(k+1)*i],cur);
			}
		}
	}
	
	sort(all.begin(),all.end(),cmp);
	int cur=0,cur_sum=0,cur_sz=0,ans=0;
	for(int i=sum;i>=0;i--)
	{
		dp[i]=min(dp[i],dp[i+1]);
		if(dp[i]<=x)
		{
			int rest=x-dp[i];
			while(cur<(int)all.size()&&(rest-cur_sum)/all[cur].ff.ss>=all[cur].ss)
			{
				cur_sum+=all[cur].ff.ss*all[cur].ss;
				cur_sz+=all[cur].ff.ff*all[cur].ss;
				cur++;
			}
			ans=max(0ll+ans,i+cur_sz+(cur<(int)all.size()?(rest-cur_sum)/all[cur].ff.ss*all[cur].ff.ff:0));
		}
	}
	printf("%d\n",ans);
	
	return 0;
}

Measured memory_bytes: 768
s = input()

flagym = 0
flagmy = 0

if 0<int(s[0:2])<= 12:
    flagmy = 1 
if 0<int(s[2:])<= 12:
    flagym = 1

if flagym ==1:
    if flagmy == 1:
        print("AMBIGUOUS")
    else:
        print("YYMM")
else:
    if flagmy == 1:
        print("MMYY")
    else:
        print("NA")


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#define MOD 1000000007

typedef long long ll;
using namespace std;

int main(void) {
    int i=0,j=0;
    string bw[60];
    bw[0]="55555555555555555555555555555555555555555555555555555";
    
    int h,w;
    cin >> h >> w;
    for(i=0;i<h;i++){
        cin >> bw[i+1];
        bw[i+1] = '.' + bw[i+1] + '.';
    }
    bw[h+1]="55555555555555555555555555555555555555555555555555555";

    int check = 0;
    for(i=1;i<h+1;i++){
        for(j=1;j<w+1;j++){
            if(bw[i][j] == '#'){
                if(bw[i-1][j] =='#' || bw[i+1][j] =='#' || bw[i][j-1] =='#' || bw[i][j+1] =='#'){
                }else{
                    check = 1;
                }
            }
        }
    }
    //    for(i=1;i<h-1;i++){
    //        for(j=1;j<w-1;j++){
    //            if(bw[i][j] == bw[i-1][j]){
    //                if(bw[i][j]=='#') check=1;
    //            }
    //            if(bw[i][j] == bw[i+1][j]){
    //                if(bw[i][j]=='#') check=1;
    //            }
    //            if(bw[i][j] == bw[i][j-1]){
    //                if(bw[i][j]=='#') check=1;
    //            }
    //            if(bw[i][j] == bw[i][j+1]){
    //                if(bw[i][j]=='#') check=1;
    //            }
    //        }
    //    }
    //    for(i=1;i<h-1;i++){
    //        if(bw[i][0] == bw[i-1][0]){
    //            if(bw[i][0]=='#') check=1;
    //        }
    //        if(bw[i][0] == bw[i+1][0]){
    //            if(bw[i][0]=='#') check=1;
    //        }
    //        if(bw[i][w-1] == bw[i-1][w-1]){
    //            if(bw[i][0]=='#') check=1;
    //        }
    //        if(bw[i][w-1] == bw[i+1][w-1]){
    //            if(bw[i][0]=='#') check=1;
    //        }
    //    }
    //    for(j=1;j<w-1;j++){
    //        if(bw[0][j] == bw[0][j-1]){
    //            if(bw[0][j]=='#') check=1;
    //        }
    //        if(bw[0][j] == bw[0][j+1]){
    //            if(bw[0][j]=='#') check=1;
    //        }
    //        if(bw[h-1][j] == bw[h-1][j-1]){
    //            if(bw[0][j]=='#') check=1;
    //        }
    //        if(bw[h-1][j] == bw[h-1][j+1]){
    //            if(bw[0][j]=='#') check=1;
    //        }
    //    }
    if(h==1 && w==1 && bw[1][1] == '#'){
        check = 1;
    }
    if(check){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int main(void){
	int box[12]={1,3,1,2,1,2,1,1,2,1,2,1};
	int x,y;
	scanf("%d %d",&x,&y);
	if(box[x-1]==box[y-1])		printf("Yes\n");
	else						printf("No\n");
	return 0;
}

Measured memory_bytes: 128
import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:h + m + 1]))

Measured memory_bytes: 3584
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n = stdIn.nextInt(); //n桁
		int m = stdIn.nextInt();
		
		boolean[] flag = new boolean[n];
		
		int[] check = new int[n]; //ある桁の場所に同じ数値が入ったかどうかcheck
		
		
		for(int i = 0; i < m; i++) {
			int s = stdIn.nextInt()-1;
			int c = stdIn.nextInt();
			
			if(s==0 && c==0 && n!=1) {
				System.out.println(-1);
				return;
			}
			
			if(flag[s]==true && check[s]!=c) {
				System.out.println(-1);
				return;
			}
			
			flag[s] = true;
			check[s] = c;
			
		}
		
		if(n==1) {
			if(flag[0]==false ) {
				System.out.println(0);
				return;
			}else {
				System.out.println(check[0]);
				return;
			}
		}
		
		for(int i = 0; i < n; i++) {
			if(flag[i]==false && i==0) {
				System.out.print(1);
			}else if(flag[i] ==false) {
				System.out.print(0);
			}else {
				System.out.print(check[i]);
			}
		}
		
	}

}


Measured memory_bytes: 21972
#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 <chrono>
#include <iostream>
#include <limits>
#include <numeric>

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int x;
  cin >> x;
  int l = 0, r = x;
  function<bool(int)> pred = [&](int t) {
    int cur = x;
    while (t) {
      if (abs(cur - t) <= cur) {
        cur = abs(cur - t);
        --t;
      } else {
        t = cur * 2;
      }
    }
    return cur == 0;
  };
  while (l < r) {
    int mid = (l + r) >> 1;
    if (pred(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l;

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


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define YES cout << "YES" << endl
#define NO  cout << "NO"  << endl
#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 1000000
using namespace std;
typedef long long ll;



int main(){
  vector<int> a;
  int s;  cin >> s;
  a.push_back(s);
  for(int i=1; i<=MAX; i++){
    if(a[i-1]%2==0){
      a.push_back(a[i-1]/2);
    }else{
      a.push_back(a[i-1]*3+1);
    }
  }
  bool isFind = false;
  for(int i=0; i<=MAX; i++){
    for(int j=i+1; j<=MAX; j++){
      if(a[i]==a[j]){
        isFind = true;
        cout << (j+1) << endl;
        break;
      }
    }
    if(isFind){
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 6512
N = int(input())
h = list(map(int,input().split()))
dp = [0, abs(h[1]-h[0])]+ [0 for i in range(N-2)]

for j in range(2,N):
    a = abs(h[j] -h[j-1]) + dp[j-1]
    b = abs(h[j] - h[j-2]) + dp[j-2]
    if a > b:
        dp[j] = b
    else:
        dp[j] = a
print(dp[-1])


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

int main()
{
	int n, m;
	int a, b;

	int outn=0, out[1000 + 10];

	int ans = 0;

	int i, j;

	int t;

	cin >> n >> m;

	for (i = 0; i < m; i++)
	{
		cin >> a >> b;

		if (a < n)
		{
			out[outn] = n - a;
			outn++;
		}
	}

	if (outn > 1)
	{
		for (i = 0; i < outn - 1; i++)
		{
			for (j = i + 1; j < outn; j++)
			{
				if (out[i] > out[j])
				{
					t = out[i];
					out[i] = out[j];
					out[j] = t;
				}
			}
			ans += out[i];
		}
	}

	cout << ans << endl;

	return 0;

}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ALL(x) (x).begin(), (x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807LL
#define LMIN -9223372036854775807LL
using ll = long long;
template<typename T>
using vec = vector<T>;
using P = pair<ll, ll>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
	fill((T *)array, (T *)(array + N), val);
}

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//ll pas[51][52];

char g[100][100];
int main(){
	IOS;
	int k = 50;
	int k2 = 100;
	int a, b;
	cin >> a >> b;
	a--;b--;
	for(int i = 0;i < k;i++){
		for(int j = 0;j < k2;j++)g[i][j] = '#';
	}
	for(int i = k;i < k2;i++){
		for(int j = 0;j < k2;j++)g[i][j] = '.';
	}
	for(int i = 0;i < k;i += 2){
		for(int j = 0;j < k2;j += 2){
			if(a > 0){
				g[i][j] = '.';
				a--;
			}
		}
	}
	for(int i = k + 1;i < k2;i += 2){
		for(int j = 0;j < k2;j += 2){
			if(b > 0){
				g[i][j] = '#';
				b--;
			}
		}
	}
	cout << 100 << " " << 100 << endl;
	REP(i,k2){
		REP(j,k2)cout << g[i][j];
		cout << endl;
	}
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int N,X,T,x;
    scanf("%d %d %d",&N,&X,&T);
    x = N / X * T;
    int k = 0;
    k = N - N /X * X ;
    if(k == 0){
        printf("%d\n",x);
        return 0;
    }
    
    if(k == 0 || k <= X){
        k = T;
        printf("%d\n",x + k);
    }
    

}

Measured memory_bytes: 1732
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
typedef long long ll;

int main()
{
	int N, M;
	scanf("%d", &N);
	char s[N][11];
	for (int i = 0; i < N; i++) scanf("%s", s[i]);
	scanf("%d", &M);
	char t[M][11];
	for (int j = 0; j < M; j++) scanf("%s", t[j]);

	int ans = 0;
	for (int k = 0; k < N; k++) {
		int buf = 1;
		for (int l = k + 1; l < N; l++) {
			if (strcmp(s[k], s[l]) == 0) buf++;
		}
		for (int m = 0; m < M; m++) {
			if (strcmp(s[k], t[m]) == 0) buf--;
		}
		
		if (ans < buf) ans = buf;
	}

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

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

#define rep(i,l,n) for(int (i)=(l);(i)<(n);(i)++)
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)

int kaibun(char*,int,int);

int main(){
	char s[100]; scanf("%s",s);
	int N=strlen(s);
	if( kaibun(s,0,N-1) && kaibun(s,0,(N-1)/2-1) && kaibun(s,(N+3)/2-1,N-1) ){
		printf("Yes");
	}else{
		printf("No");
	}
	return 0;
}

int kaibun(char *s,int a,int b){
	while(a<b){
		if( *(s+a)==*(s+b) ){
			a++; b--;
		}else{
			return 0;
		}
	}
	return 1;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> xs(1 << n);
    for (int& x : xs) {
        cin >> x;
    }
    multiset<int, function<bool(int, int)>> potential_slimes(xs.begin(), xs.end(), [](int a, int b) { return a > b; });
    vector<int> realized_slimes = {*potential_slimes.begin()};
    potential_slimes.erase(potential_slimes.begin());
    for (int t = 0; t < n; ++t) {
        for (int i = 0; i < (1 << t); ++i) {
            auto it = potential_slimes.upper_bound(realized_slimes[i]);
            if (it == potential_slimes.end()) {
                cout << "No" << endl;
                return 0;
            }
            realized_slimes.push_back(*it);
            potential_slimes.erase(it);
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 14840
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

#define INF (1 << 28)

using namespace std;

int main(){
	
	int M, N;
	
	cin >> M >> N;
	
	int P[20000];
	
	for(int i = 0; i < M; i++){
		cin >> P[i];
	}
	
	sort(P, P + M);
	
	int DP[20000];
	
	for(int i = 0; i < 20000; i++){
		DP[i] = INF;
	}
	
	DP[0] = 0;
	
	for(int i = 0; i < N; i++){
		int num, cost;
		cin >> num >> cost;
		for(int j = 10001 - num; j >= 0; j--){
			DP[j + num] = min(DP[j + num], DP[j] + cost);
		}
		for(int j = 10001; j >= 0; j--){
			DP[j] = min(DP[j], DP[j + 1]);
		}
	}
	
	int sum = 0;
	
	int ans_max = 0;
	
	for(int i = 1; i <= M; i++){
		sum += P[M - i];
		if(ans_max < sum - DP[i]){
			ans_max = sum - DP[i];
		}
	}
	
	cout << ans_max << endl;
	
	return 0;
}

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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

ll n;

ll add(ll x, ll y){
    if(y < 0){
        return (x + y + n) % n;
    }else{
        return (x + y) % n;
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n; cin >> n;
    ll a[n];
    ll sum = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        sum += a[i];
    }
    ll sumn = n * (n + 1) / 2;
    if(sum % sumn != 0){
        cout << "NO" << endl;
        return 0;
    }
    ll ops = sum / sumn;
    ll d[n];
    for(int i=0;i<n-1;i++){
        d[i] = a[i+1] - a[i];
    }
    d[n-1] = a[0] - a[n-1];
    // finally, all d is 0
    for(int i=0;i<n;i++){
        if((ops - d[i]) < 0 || (ops - d[i]) % n != 0){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

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

int main() {
  //文字列を代入する
  string word;
  cin >> word;
  
  //aの一番手前の位置を代入
  int a;
  for (int i = 0; i < word.size(); i++) {
    if (word.at(i) == 'A') {
      a = i;
      break;
    }
  }
  
  //zの一番最後の位置を代入
  int z;
  for (int j = 0; j < word.size(); j++) {
    if (word.at(j) == 'Z') {
      z = j;
    }
  }
  
  //間の数を出力
  cout << z-a+1 << endl;
    
}

Measured memory_bytes: 640
n = int(input())
k = int(input())
import math

def nine(x, y):
  if y == 0:
    return 1
  elif x < y:
    return 0
  elif x == y:
    return 9 ** x
  elif y < 0:
    return 0
  else:
    r = 1
    for i in range(y):
      r *= x - i
      r //= i + 1
    r *= 9 ** y
    return r

ans = 0
if n > 10000:
  while n >= 10**(k-1):
    d = math.floor(math.log(n, 10))
    ans += nine(d, k)
    ans += nine(d, k-1) * (n//(10**d) - 1)
    n %= 10**d
    if k > 0:
      k -= 1
    else:
      break
  print(ans)
else:
  for i in range(1,n+1):
    if str(i).count('0')==len(str(i))-k:
      ans += 1
  print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<climits>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
#include<iterator>
#include<queue>
#include<stack>
#include<cctype>
#include<deque>

//by Skeef79

//НЕ ИСПОЛЬЗУЙ endl, есть свой en!!
//Иногда нужно не просто придумывать решение, а метматически расписать систему уравнений
//для задач с cin/cout в большом кол-ве - gnu , иначе вижуалки. А ваще пробуй два если TL

//для интерактивок - cout<<flush
// cin.tie и sync_with_stdio убирать для интерактивок

typedef long long ll;
typedef long double ld;

#define pb push_back
#define en '\n'
#define for0(i,n) for(int i = 0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()

using namespace std;

const int INF = 1e9 + 1233;
const ll LINF = 1e18 + 1233;

template<typename T> void print(vector<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
}

template <typename T> void Input(vector<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cin >> a[i];
}


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

	int n;
	cin >> n;
	
	map<string, ll> mp;

	for (int i = 0; i < n; i++)
	{
		vector<char> tek(10);

		for (int j = 0; j < 10; j++)
			cin >> tek[j];

		sort(all(tek));
		string g;
		for (auto to : tek)
			g += to;

		mp[g]++;

	}

	ll res = 0;

	for (auto to : mp)
	{
		res += (to.second * (to.second - 1) / 2);
	}

	cout << res;

}





Measured memory_bytes: 12800
/*<<head>> {{{*/
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
#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 fi first
#define se second
//INF = 1 061 109 567 ; INF + INF = 2 122 219 134 ;
//LINF = 4 557 430 888 798 830 399 ; LINF + LINF = 9 114 861 777 597 660 798 ;
const int INF = 0x3f3f3f3f;     // -INF: 0xc0   abs(-INF) = INF + 1
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/*}}}*/                         // zr, zm
const int MOD = (int)1e9+7;     // when MOD = 1e9+7, inv2 = 500000004
const int N = (int)1e6+7;

// ------- 变量 ------- //

int a;
char s[N];

// ------- 函数 ------- //

void Init() {
    
}

int Solve() {
    return puts(a >= 3200 ? s : "red");
}

// ------- main ------- //

int main ()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    //Pre();
    //int t; scanf("%d", &t); while (t--) {
    while (~scanf("%d%s", &a, s)) {
    //while(fgets(s, N, stdin)) {   // 注意 fgets 会读入换行符
        //if (n == 0) break;
        //static int kase = 0; printf("Case %d: ", ++kase);
        Init();
        Solve();
        //if (t) puts("");
    }
    return 0;
}

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

#define FALSE 0
#define TRUE  1

#define MIN(a, b) ((a)<(b) ?  (a) : (b))
#define MAX(a, b) ((a)>(b) ?  (a) : (b))
#define ABS(a) 	((a)< 0  ? -(a) : (a))
#define IMPAR(a)	((a)&1)
#define CTOI(a)	((a) - '0')
#define ITOC(a)	((a) + '0')

#define MAX_TAM	100

typedef struct {int custo, votos;} TMelhoria;

// Variaveis do knapsack
int xi, xw, MW, C[MAX_TAM + 1][10001], V[MAX_TAM + 1][10001];

int main()
{	int N, T, L, l;
	TMelhoria melhorias[MAX_TAM];
	char possivel;
	unsigned t = clock();
	
	while (scanf("%d %d", &L, &T) != EOF)
	{	for (l = 0, possivel = FALSE; l < L; l++)
		{	scanf("%d %d", &melhorias[l].votos, &melhorias[l].custo);
			if (melhorias[l].custo <= T )
				possivel = TRUE;
		}
/*		
		for (l = 0; l < L; l++)
			printf("%d %d\n", melhorias[l].votos, melhorias[l].custo);
		printf("\n\n");
*/		
		if (!possivel)
			puts("-1");
		else
		{ //The solution can be found in C[N][W];
			MW = T;			// Tamanho da mochila
	
			for (xi = 0; xi <= L; xi++)
				C[xi][0] = V[xi][0] = 0;
			
			for (xw = 0; xw <= MW; xw++) 
				C[0][xw] = V[0][xw] = 0;
			
			for (xi = 1; xi <= L; xi++)
				for (xw = 1; xw <= MW; xw++)
				{	if (melhorias[xi - 1].custo > xw)
					{	C[xi][xw] = C[xi - 1][xw];
						V[xi][xw] = V[xi - 1][xw];
					}
					else
						if (C[xi - 1][xw] > C[xi - 1][xw - melhorias[xi - 1].custo] + melhorias[xi - 1].votos)
						{	C[xi][xw] = C[xi - 1][xw];
							V[xi][xw] = V[xi - 1][xw];
						}
						else
						{	C[xi][xw] = C[xi - 1][xw - melhorias[xi - 1].custo] + melhorias[xi - 1].votos;
							V[xi][xw] = V[xi - 1][xw - melhorias[xi - 1].custo] + melhorias[xi - 1].custo;
						}
				}
			printf("%d\n", C[L][MW]);
/*			
			for (xi = 0; xi <= L; xi++)
			{	for (xw = 0; xw <= MW; xw++)
					printf("%2d ", C[xi][xw]);
				printf("\n");
			}
			printf("*************************\n");
*/		}
	}
	
//	printf("\n\n%d\n ", (clock()-t) / CLK_TCK);
	
	return 0;
}

Measured memory_bytes: 8496
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}
const LL N = 50;
VEC<LL> total(N + 1, 0);
VEC<LL> paty(N + 1, 0);

LL num_paty(LL level, LL run) {
  if(run==0)return 0;
  if (level == 0) {
    if (run >= 1) {
      return 1LL;
    } else
      return 0LL;
  } else {
    if (run <= 1) {
      return 0;
    } else if (run < total[level] / 2 + 1)
      return num_paty(level - 1, run - 1);
    else if (run == total[level] / 2 + 1)
      return paty[level - 1] + 1;
    else if (run < total[level])
      return num_paty(level - 1, run - total[level] / 2 - 1) + paty[level - 1] +
             1;
    else
      return paty[level];
  }
}

int main() {
  LL n, x;
  cin >> n >> x;
  LL num = 1;
  LL npaty = 1;
  REPC(i, 0, N) {
    total[i] = num;
    num = 2 * num + 3;
    paty[i] = npaty;
    npaty = 2 * npaty + 1;
  }
  // DUMP(total);
  // DUMP(paty);
  cout << num_paty(n, x) << endl;

  return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    if i==n-1:
        print(a[i])
    else:
        print(a[i],end=' ')
for i in range(1,n):
    v=a[i]
    j=i-1
    while j>=0 and a[j]>v:
        a[j+1]=a[j]
        j-=1
    a[j+1]=v
    for i in range(n):
        if i==n-1:
            print(a[i])
        else:
            print(a[i],end=' ')


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

typedef long long ll;
int ara[60];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    vector<ll>v;
    for(ll i=0;i<n;i++)
    {
        ll a;
        cin>>a;
        v.push_back(a);
    }
    ll cnt=0;
    ll var=v[0];
    ll ans=0;
    for(ll i=1;i<v.size();i++)
    {
        if(v[i]>var)
        {
            cnt=0;
            var=v[i];
        }
        else
        {
            cnt++;
            var=v[i];
        }
        ans=max(cnt,ans);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define ref1(i,s,e,c) for(int i=s;i<e;i=i+c)
#define ref2(i,s,e,c) for(int i=s;i<=e;i=i+c)
#define ref3(i,e,s,c) for(int i=e;i>=s;i=i-c)
using namespace std;
typedef long long ll;
const int MAXSIZE=100005;
int main()
{
    int arr[5],k;
    ref1(i,0,5,1){
    	cin>>arr[i];
	}
	cin>>k;
	sort(arr,arr+5);
	if(arr[4]-arr[0]>k){
		cout<<":(\n";
	}
	else{
		cout<<"Yay!\n";
	}
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	string s;
	cin>>n>>s;
	int x=0;
	int big=0;
	for(int i=0;i<n;i++){
		if(s[i]=='I'){
			x++;
		}
		else{
			x--;
		}
		if(x>big)big=x;
	}
	cout<<big<<endl;
	return 0;
}
		


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin >> s >> t;
    ll ans = 1e9;
    ll ct = 0;
    for(int i=0; i<s.length()-t.length()+1; i++){
        ct = 0;
        for(int j=0; j<t.length(); j++){
            if(s[j+i] != t[j]){
                ct += 1;
            }
        }
        ans = min(ans, ct);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3680
k,n = map(int, input().split())
A = input().split()
A = [int(a) for a in A]
for i in range(n):
  A.append(A[i])

min = k
for i in range(n):
  if A[i+n-1]>=A[i]: 
    d = A[i+n-1]-A[i]
  else:
    d = A[i+n-1]+k-A[i]
  if d<min: min = d
    
print(min)

Measured memory_bytes: 26436
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define ll long long
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vector<int>,greater<int>>
const double pi = acos(-1.0);
const double eps = 1e-6;
using namespace std;


const int N = 1e5 + 1;
int n, m;
ll p[N], q[N], pref[N];
void solve(){ 
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    for (int i = 1; i <= m; i++)
        cin >> q[i];
    
    ll sum = 0;

    for (int i = 1; i <= n; i++) sum += p[i];
    for (int i = 1; i <= m; i++) sum += q[i];

    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i++)
        pref[i] += pref[i - 1] + p[i];

    for (int i = 1; i <= m; i++){
        int pos = upper_bound(p + 1, p + n + 1, q[i]) - p;
        //cout << pos << endl;
        sum += pref[pos - 1] + (n - pos + 1) * 1ll * q[i]; 
    }
    cout << sum << endl;
}       
int main(){
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(5);
    //freopen("input.txt", "r", stdin);//freopen("output1.txt", "w", stdout);
    //freopen("icecream.in","r",stdin);// freopen("exam.out", "w", stdout);
    int step;
    step = 1;
    //cin >> step;
    for (int i = 1; i <= step; i++){
         solve();
    }
}

Measured memory_bytes: 5968
h, w, a, b = gets.chomp.split(" ").map(&:to_i)

MOD = 10**9 + 7

def power(x, n)
  if n == 0
    return 1
  elsif n.even?
    return power(x * x, n / 2) % MOD
  else
    return x * power(x, n /2)**2 % MOD
  end
end

@fac = []
@fac[0] = @fac[1] = 1

2.upto(h + w - 2) do |i|
  @fac[i] = @fac[i - 1] * i % MOD
end

@faci = []
@faci[0] = @faci[1] = 1
@faci[h + w - 2] = power(@fac[h + w - 2], MOD - 2) % MOD
(h + w - 3).downto(2) do |i|
  @faci[i] = @faci[i + 1] * (i + 1) % MOD
end


def comb(n, k)
  return 0 if n < k
  return 0 if n < 0 || k < 0
  return @fac[n] * (@faci[k] * @faci[n - k] % MOD) % MOD
end

ans = 0

b.upto(w - 1) do |i|
  ans += comb(h - a - 1 + i, i) * comb(a + w - i - 2, w - i - 1)
  ans %= MOD
end
p ans % MOD



Measured memory_bytes: 6276
n,m=map(int,input().split())
l=[]
k=['_']*m
x=[1]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    l.append([i,a,b])
y=sorted(l,key=lambda c:c[2])
for i in y:
    k[i[0]]=str(i[1]).zfill(6)+str(x[i[1]]).zfill(6)
    x[i[1]]+=1
for i in k:
    print(i)

Measured memory_bytes: 32972
#include <stdio.h>
#include <stdlib.h>
long xxx[10][901][101];

long pattern(int n,int s,int from){
	long i,x=0;
	if(s>100*n)return 0;
	if(xxx[n][s][from]>=0)x=xxx[n][s][from];
	else{
		for(i=(s-100*(n-1)>from?s-100*(n-1):from); i<100 && i*n<=s ;i++){x+=pattern(n-1,s-i,i+1);}
		xxx[n][s][from]=x;
	}
	return x;
}

int main(void){
	int n,s,i,j,k;
	for(j=0;j<101;j++){for(k=0;k<101;k++){xxx[1][j][k]=( (j<=100 && k<=j)?1:0 );}}
	for(j=0;j<201;j++){for(k=0;k<101;k++){xxx[2][j][k]=( (2*k<=j && j<=200) ? ((100-k+1)-abs((100-k)-(j-k*2)))/2 : 0 );}}
	for(i=3;i<10;i++){for(j=0;j<=i*100;j++){for(k=0;k<101;k++){xxx[i][j][k]=-1;}}}
    while(scanf("%d %d",&n,&s)*(n+s)){
	printf("%ld\n",pattern(n,s,0));}
    return 0;
}

Measured memory_bytes: 5844
// C - Rally
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
template<class T>bool chmin(T &a, const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T> vector<T> inarr(int s,int e, T init){
	vector<T> v;T x;
	for(int i=0;i<s;++i)v.push_back(init);
	for(int i=s;i<e;++i){cin>>x;v.push_back(x);}
	return v;
}

int N;
vi X;

int solve(){
	int ans = INT_MAX;
	sort(all(X));
	rp(p, X[0], X[N-1]+1){
		int wa = 0;
		for(auto x:X) wa += (x-p)*(x-p);
		chmin(ans, wa);
	}
	return ans;
}

int main(){
	cin>>N;
	X = inarr<int>(0,N,0);
	cout<< solve() <<endl;
}

Measured memory_bytes: 256