akhauriyash/Code-Regression huggingface dataset:
/*
 * 	The way if it's all predetermined
 * 		And the way i should go all my life
 * 			I swear to go wherever will be
 * 				'Cause there'll be something to see and to find
 */
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifdef rd
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
#else
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=4e18;
const int infi=1e9;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(ll a, ll b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

bitset<100005> hola[100005];
vi px[100005];
set<int> pxx[100005];
int dsu[100005];
int fpar(int i) {
	return (dsu[i]<0)?i:dsu[i]=fpar(dsu[i]);
}
void merge(int i, int j) {
	if((i=fpar(i))!=(j=fpar(j))) {
		if(dsu[i]>dsu[j])
			swap(i,j);
		dsu[i]+=dsu[j];
		dsu[j]=i;
	}
}
void solve() {
	int n;
	memset(dsu,-1,sizeof(dsu));
	cin>>n;
	fr(i,1,n) {
		int x,y;
		cin>>x>>y;
		px[x].pb(y);
	}
	fr(i,1,100000) {
		for(int j=0; j+1<px[i].size(); j++) {
			merge(px[i][j],px[i][j+1]);
		}
	}
	fr(i,1,100000) {
		for(int j:px[i]) {
			pxx[fpar(j)].insert(i);
			break;
		}
	}
	int ans=0;
	fr(i,1,100000) {
		if(dsu[i]<0) {
			ans=(ans+(-dsu[i])*(sz(pxx[i])));
		}
	}
	cout<<ans-n<<endl;
}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
#ifdef rd
	cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}


Measured memory_bytes: 12672
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <functional>
#include <string>
#include <array>
#include <vector>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <complex>
#define full(c) c.begin(), c.end()
#define vector2d(name,type,h,w,init) vector<vector<type>> name(h,vector<type>(w,init)) 
const int PRIME = 1000000007;
const int INT_INF = 2147483647;
const long long int LL_INF = 9223372036854775807;
const double PI = acos(-1);
const double EPS = 0.000000001;
typedef unsigned long long int ull;
typedef long long int ll;
using namespace std;

int main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	ll i, N, n0 = 0, n2 = 0, n4 = 0;
	cin >> N;
	for (i = 0; i < N; i++){
		int a;
		cin >> a;
		if (a % 4 == 0) n4++;
		else if (a % 2 == 0) n2++;
		else n0++;
	}
	if (2 * n4 + 1 >= N) cout << "Yes" << endl;
	else if (2 * n4 + n2 >= N) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int n = sc.nextInt();
		boolean[] array = new boolean[800];
		Arrays.fill(array, true);
		for (int i = 0; i < n; i++) {
			array[sc.nextInt() + 400] = false;
		}
		int res = -100;
		for (int i = 0; i < 300; i++) {
			if (array[x - i + 400]) {
				res = x - i;
				break;
			}
			if (array[i + x + 400]) {
				res = i + x;
				break;
			}
		}
		System.out.println(res);
	}
}


Measured memory_bytes: 35936
// Java program For handling Input/Output 
import java.io.*; 
import java.util.*;
import java.math.*;
//import java.awt.*;

public class Main 
{ 
    FastReader sc;
    //actual logic
    void solve(){
        char c = sc.ns().charAt(0);
        System.out.println((char)(c+1));

    }
    
    //constructor
    Main()
    {
        try{  
            sc = new FastReader();
        }catch(Exception e){
            System.out.println(e);
        }
    }


    //main metohd
    public static void main(String[] args)
    { 
     new Main().solve();
    }
    //Utility methods

    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
            try{
                st = new StringTokenizer(br.readLine());
            }catch(Exception e){
                System.out.println(e);
            }
        }

        FastReader(String s){
            try{
                br = new BufferedReader(new FileReader(s));
                st = new StringTokenizer(br.readLine());
            }catch(Exception e){
                System.out.println(e);
            }
        }

        String ns(){
            if(!st.hasMoreTokens())
            {
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(Exception e){
                    System.out.println(e);
                }    
            }
            return st.nextToken();

        }

        int ni(){
            return Integer.parseInt(ns());
        }

        long nl(){
            return Long.parseLong(ns());
        }

        double nd(){
            return Double.parseDouble(ns());
        }
    }
}


Measured memory_bytes: 19028
using System;
using System.Text;
using System.Collections.Generic;

namespace Aizu
{
    class OnlineJudge
    {
        public static void Main()
        {
            int count = int.Parse(Console.ReadLine());
            var hash = new HashSet<string>();
            var output = new StringBuilder(4000000);
            for (int i = 0; i < count; ++i) {
                var input = Console.ReadLine().Split();
                if(input[0] == "insert") {
                    hash.Add(input[1]);
                }
                else {
                    output.AppendLine(hash.Contains(input[1]) ? "yes" : "no");
                }
            }
            Console.Write(output.ToString());
        }
    }
}

Measured memory_bytes: 49364
from heapq import heappush,heappop,heapify

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
change = [list(map(int,input().split())) for _ in range(M)]

def tempchange(l,change):
  heapify(l)  
  for B,C in change:
    for j in range(B):
      a = heappop(l)
      if C - a > 0:
        heappush(l,C)
      else:
        heappush(l,a)
        break
  return sum(l)

#A.sort(reverse = True)
change.sort(key = lambda x:x[1],reverse =True)
print(tempchange(A,change))

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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
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 (a>b) { a=b; return 1; } return 0; }

using ll = long long;

using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr double PI = acos(-1);

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

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 {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=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 {
    mint res(*this);
    return res/=a;
  }
};
 

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin>>n;
ll zero=0;
map<pair<ll,ll>,pair<int,int>> mp;

rep(i,n){
    ll x,y;
    cin>>x>>y;
    if(x==0&&y==0){
        zero++;
        continue;
    }
    ll g = gcd(x,y);
    x/=g;
    y/=g;

    if(y<0){
        x=-x,y=-y;
    }
    if(y==0&&x<0){
        x=-x;
        y=-y;
    }
    bool rot90=(x<=0);
    if(rot90){
        ll tmp=x;
        x=y,y=-tmp;
    }
    if(rot90)mp[{x,y}].first++;
    else mp[{x,y}].second++;
}

mint ans=1;

for(auto v: mp){
    int s=v.second.first;
    int t=v.second.second;
    mint now=1;

    now+=mint(2).pow(s)-1;
    now+=mint(2).pow(t)-1;
    ans*=now;
}
ans-=1;
ans+=zero;
cout<<ans.x<<endl;
return 0;
}

Measured memory_bytes: 16076
def imp():return map(int,input().split())
h,w=imp()
l=[]
for _ in range(h):
    s=input()
    if '#' in s:l.append([x for x in s])

ans=[]
for j in range(w):
    s=""
    for i in range(len(l)):
        s+=l[i][j]
    if '#' in s: ans.append([x for x in s])

w=len(ans[0])
for j in range(w):
    s=""
    for x in ans:
        s+=x[j]
    print(s)







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

int main()
{
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;

    rep(i,n){
        cout<<s[i];
        cout << t[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int i=0,j;
	char a[1000]={0};
	scanf("%s",a);
	while(a[i]!=0)++i;
	for(j=0;j<i;j++){
		if(a[j]=='A' || a[j]=='B' || a[j]=='C')a[j]+=26;
		printf("%c",a[j]-3);
	}
	printf("\n");
	return 0;
}


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

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

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

Measured memory_bytes: 256
/*
author: Apoorv Singh
*/

#include <bits/stdc++.h>
using namespace std;

typedef vector <long long> vi;
typedef pair <long long, long long> pii;
#define pb push_back   
#define all(c) c.begin(), c.end()
#define watch(x) cout << (#x) << " " << (x) << endl;
#define FOR(i, a, b) for (long long i = a; i < b; ++i)
#define FORR(i, a, b) for (long long i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second
#define int long long
#define inf LLONG_MAX
#define endl "\n"

int modulo = 1e9 + 7;

template <class X>

void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int fpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a)%modulo;
        a = (a*a)%modulo;
        n = n >> 1;
    }
    return ans;
}

/*
const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}
*/

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int p,q,r; cin >> p >> q >> r;
    cout << min({p+q, q+r, r+p});
    return 0;
}

Measured memory_bytes: 256
def rle(a):
    ll,l=[],1
    for i in range(len(a)-1):
        if a[i]==a[i+1]:
            l+=1
        else:
            ll.append([l,a[i]])
            l=1
    ll.append([l,a[-1]])
    return ll
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
ans=0
w=[]
for i in range(k):
    j=i
    b=""
    while j<n:
        b+=t[j]
        j+=k
    w.append(b)
for i in t:
    if i=="r":
        ans+=p
    elif i=="s":
        ans+=r
    else:
        ans+=s
for x in w:
    st=rle(x)
    for i,j in st:
        if j=="r":
            ans-=(i//2)*p
        elif j=="s":
            ans-=(i//2)*r
        else:
            ans-=(i//2)*s
print(ans)

Measured memory_bytes: 17984
// Library
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// TYPEDEFS
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

// CONSTANTS
#define SZA 0
#define SZB 0

// MACRO
#define MAX(X, Y) (((X) > (Y))? (X) : (Y))
#define MIN(X, Y) (((X) < (Y))? (X) : (Y))
#define ABS(X) (((X) > 0)? (X) : -(X))
#define YN(X) ((X)? "YES" : "NO")
#define SWAP(T, X, Y) {T t; t = X; X = Y; Y = t;}

#define F first
#define S second
#define PB push_back
#define MP make_pair


// Global Tables

//ull gPreProcess[SZA][SZB];

// Functions

void Print2DVector(vector<vector<int>>& v)
{
    ull i, j; 
    for(i = 0; i < v.size(); i++)
    {
        for(j = 0; j < v[i].size(); j++)
        {
            cout << v[i][j];
            if(j == v[i].size()-1)
            {
                cout << endl;
            }
            else
            {
                cout << " ";
            }
        }
    }
}

void PrintVector(vi& v)
{
    ull i;
    for(i = 0; i < v.size(); i++)
    {
        cout << v[i];
        if(i == v.size()-1)
        {
            cout << endl;
        }
        else
        {
            cout << " ";
        }
    }
}

void PrintArr(int* a, ull N)
{
    ull i;
    for(i = 0; i < N; i++)
    {
        cout << a[i];
        if(i == N-1)
        {
            cout << endl;
        }
        else
        {
            cout << " ";
        }
    }
}

void PreProcessTables()
{
    ull i, j;
    for(i = 0; i < SZA; i++)
    {
        for(j = 0; j < SZB; j++)
        {
            break;
        }
        break;
    }
}

void TC(int t)
{
    ull A, B, C, K;
    ll out = 0;
    cin >> A >> B >> C >> K;
    if(A < K)
    {
        out += A;
        if(A + B < K)
        {
            out -= (K - (A+B));
        }
    }
    else
    {
        out = K;
    }
    cout << out << endl;
}

// Main

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

    int T = 1, t;
    for(t = 1; t <= T; t++)
    {
        TC(t);
    }
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
 
using namespace std;
 
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
 
long gcd(long a, long b){
	if (a%b==0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}
}
 
long lcm(long a, long b){
	return (a*b) / gcd(a,b);
}
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a < b) { a = b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a > b) { a = b; return 1; } return 0; }

typedef long long ll;

const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS = 1e-10;

char s[102345];
char st[4][10] = {
	{"maerd"},
	{"remaerd"},
	{"esare"},
	{"resare"}
};
int t[4] = {5,7,5,6};

int main(){
	scanf("%s", s);
	
	int len = strlen(s);
	
	int flag = 0;
	
	REP(i,len){
		REP(j,4){
			if (s[len-i-1] == st[j][0]){
				flag = 0;
				REP(k,t[j]){
					if (s[len-i-1-k] != st[j][k]) flag = 1;
				}
				
				if (flag == 0){
					i += t[j]-1;
					break;
				}
			}
			else {
				flag = 1;
			}
		}
		if (flag) break;
	}
	
	if (flag) cout << "NO" << endl;
	else cout << "YES" << endl;
	
	return 0;
}

Measured memory_bytes: 384
def main():
    import re
    s = input()

    if s[0] == "A":
        s1 = s[2:-1]
        if s1.count("C") == 1:
            s2 = re.sub(r'[a-z]', '', s)
            if len(s2) == 2:
                print("AC")
                return
    print("WA")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

int main()
{
	for(string s;getline(cin,s) && s!="0";){
		int n=s.size();
		vvi dp(11,vi(n+1));
		rep(i,n){
			if(s[i]!='0') dp[s[i]-'0'][i+1]++;
			rep(j,11){
				int k=(j*10+s[i]-'0')%11;
				dp[k][i+1]+=dp[j][i];
			}
		}
		cout<<accumulate(all(dp[0]),0)<<endl;
	}
}

Measured memory_bytes: 5092
#include<iostream>
#include<vector>
#include<cstdio>
#define MN 1000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
long long res1,res2;
int n,a[MN+5],mx=-1e9,b[MN+5];
int main()
{
	n=read();
	for(int i=1,j;i<=n;++i)
	{
		a[i]=read();mx=max(mx,a[i]);
		if(i&1) res1+=max(a[i],0);
		else res2+=max(a[i],0);
	}
	if(mx<=0)
	{
		cout<<mx<<endl;
		for(int i=1;i<=n;++i) if(a[i]==mx)
		{
			printf("%d\n",n-1);
			for(int j=n;j>i;--j) printf("%d\n",j);
			for(int j=1;j<i;++j) printf("%d\n",1);
			return 0;
		}
	}
	printf("%lld\n",max(res1,res2));
	vector<int> ans;int num=0;
	if((res1>=res2&&(~n&1))||(res1<res2&&(n&1))) ans.push_back(n),--n;
	for(int i=n;i>0;i-=2)
	{
		if(a[i]<=0)
		{
			if(i==n||i==1) ans.push_back(i),ans.push_back((i==n)?i-1:i),(i==n)?n-=2:0;
			else ans.push_back(i);	
		}
		else ++num;
	}
	if(res1<res2) ans.push_back(1);
	for(;num>1;--num) ans.push_back(2);
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();++i) printf("%d\n",ans[i]);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define intMax 2147483647
#define rep(i, a, b) for (long long i = a; i < b; i++)
#define repp(i, a, b) for (long long i = a; i >= b; i--)
#define be(a) (a.begin(), a.end())
#define rbe(p) (p.rbegin(), p.rend())
#define pb push_back
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n , a , b;
    cin >> n >> a >> b;
    cout << min(b,n*a);
}

Measured memory_bytes: 256
/// Bismillahir Rahmanir Rahim
//Author: Tanvir Hussain
//ICE,NSTU
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std;

const long long MOD = 1000000007;
#define SET(x) memset(x, 0, sizeof(x))
#define SET2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define SETBOOL(x) memset(x,false,sizeof(x))
#define CLR(x) memset(x, -1, sizeof(x))
#define mp make_pair
#define PII pair<int, int>
#define pf printf

#define sf scanf

#define ALL(x) x.begin(),x.end()
#define pb push_back

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define np std::string::npos
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define cases(cs,t) for(int cs=1;cs<=t;cs++)
#define PI acos(-1)
#define no1 __builtin_popcount
#define BOUNDARY(i, j) ((i >= 0 && i < row) && (j >= 0 && j < column))
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define sz(a) int(a.size())
#define ff first
#define ss second
#define endl "\n"
#define forch(it,s) for(auto it:s)
#define each(it,s) for(auto it = s.begin(); it != s.end(); ++it)
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const int maxx=100005;

//this fuction sorts vector pair according to first element in descending order.
bool sortinrev(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}

template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
double sq(double x) {return x*x;}
int ext_gcd(int a, int b, int & x, int & y) {
    //for finding modular inverse
    //if its return 1 ,then a has a mod inverse x mod b.
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    int x1, y1;
    int d = ext_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
void solve(){

}

int main()

{
    IOS;
    /*#ifndef ONLINE_JUDGE
        freopen ("data.in","r",stdin);
        freopen ("data.out","w",stdout);
    #endif*/
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll sum=0;
    while(k){
        sum+=min(a,k);
        k-=min(a,k);
        if(k<=0) break;
        k-=min(b,k);
        if(k<=0) break;
        sum-=min(c,k);
        k-=min(c,k);
    }
    cout<<sum<<endl;

     return 0;

}
///Alhamdulillah



Measured memory_bytes: 3612
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	int N, H, W;
	
	cin >> N >> H >> W;

	cout << (N-H+1) * (N-W+1) << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

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

    int ans = (a > b) ? a-1 : a;

 #if 0   
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            if (i == j) {
                ans++;
                break;
            }
        }
    }
 #endif   

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;


int main() {
    ll N;
    cin >> N;
    vector<ll> A;
    for (ll i = 0;i<N;i++) {
        ll a;
        cin >> a;
        A.push_back(a);
    }    
    sort(A.begin(),A.end());
    vector<ll> wa(N);
    ll w = 0;
    for (ll i = 0;i<N;i++) {
        w += A.at(i);
        wa.at(i) = w;
    }
    ll cnt = 0;
    bool kieru = false;
    for (ll i = 0;i<N-1;i++) { 
        if (wa.at(i) * 2 < A.at(i+1)) {
            cnt = max(cnt,i);
            kieru = true;
        }
    }
    if (kieru) cout << N -cnt-1 << endl;
    else cout << N << endl;
}

Measured memory_bytes: 1908
#include<stdio.h>

int main(){

	int a, b, c,count=0,i;

	scanf("%d %d %d", &a, &b, &c);

	if (a<=b)
	{

		for ( i = a; i <= b; i++)
		{

			if (c%i==0)
			{
				count += 1;
			}

		}


	}

	printf("%d\n", count);


	return 0;
}

Measured memory_bytes: 596
#include <iostream>

using namespace std;

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

	for (int i = M / N; i >= 1; --i)
	{
		if (M % i == 0)
		{
			cout << i << endl;
			return 0;
		}
	}
}
  

Measured memory_bytes: 256
N = int(input())
a = list(map(int, input().split()))

a_sub_i = []
for i in range(N):
    a_sub_i.append(a[i]-(i+1))

a_sub_i.sort()

if N%2==1:
    b = a_sub_i[N//2]
else:
    b = (a_sub_i[N//2-1] + a_sub_i[N//2]) // 2

sadness = 0
for i in range(N):
    sadness += abs(a_sub_i[i] - b)
print(sadness)

Measured memory_bytes: 30692
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {
    
    int N, M;
    cin >> N >> M;
    if (N == M) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,y;cin >> n >> y;
	rep(i,n+1){
		for(int j=0;i+j<n+1;++j){
			int k=n-i-j;
			if(i*10000+j*5000+k*1000==y){
				cout << i << " " << j << " " << k << endl;
				return 0;
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
std::string m[12];
void d(int x,int y){
	if(x>0&&m[y][x-1]-'0')m[y][x-1]='0',d(x-1,y);
	if(x<11&&m[y][x+1]-'0')m[y][x+1]='0',d(x+1,y);
	if(y>0&&m[y-1][x]-'0')m[y-1][x]='0',d(x,y-1);
	if(y<11&&m[y+1][x]-'0')m[y+1][x]='0',d(x,y+1);
	return ;
}
int main(){
	while(1){
		int y=12;
		for(;y;y--)
			std::cin>>m[y-1];
		if(std::cin.eof())return 0;
		int r = 0;
		for(y=0;y<12;y++){
			for(int x=0;x<12;x++)
				if(m[y][x]-'0')r++,m[y][x]='0',d(x,y);
		}
		std::cout<<r<<'\n';
	}
}

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

int main() {
    ll h, w;
    cin >> h >> w;
    if (h == 1 || w == 1){
        cout << 1 << endl;
    }else if(h * w % 2 == 1){
        cout << h * w / 2 + 1 << endl;
    }else if(h * w % 2 == 0){
        cout << h * w / 2 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
using namespace std;
struct POS{
  int x;
  int y;
};
long long n,field[1001][1001],dp[1001][1001];
int h,w;
int main(){
  while(cin >>h>>w>>n,h||w||n){
    memset(dp,0,sizeof(dp));
    memset(field,0,sizeof(field));
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
	cin >>field[j][i];
      }
    }
    dp[0][0] = n-1;
    for(int i=0; i<w; i++){
      for(int j=0; j<h; j++){
 	if(dp[i][j]>0){
	  if(dp[i][j]%2 == 0){
	    dp[i+1][j]+=dp[i][j]/2;
	    dp[i][j+1]+=dp[i][j]/2;
	  }
	  else{
	    if(field[i][j] == 0){
	      dp[i+1][j]+=dp[i][j]/2;
	      dp[i][j+1]+=dp[i][j]/2+1;
	    }
	    if(field[i][j] == 1){
	      dp[i+1][j]+=dp[i][j]/2+1;
	      dp[i][j+1]+=dp[i][j]/2;
	    }
	  }
	}
      }
    }
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
	field[j][i] = (field[j][i]+dp[j][i]%2)%2;
      }
    }
    int px = 0,py = 0;
    while(px<w && py<h){
      if(field[px][py] == 0){py++;}
      if(field[px][py] == 1){px++;}
    }
    cout <<py+1<<" "<<px+1<<endl;
  }
  return 0;
}

Measured memory_bytes: 16832
#include <stdio.h>

int main(void)
{
	int n,m,a[100][100],b[100],c[100],i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",&a[i][j]);
	for(i=0;i<m;i++)scanf("%d",&b[i]);
	for(i=0;i<n;i++)for(j=0;j<m;j++)c[i]+=a[i][j]*b[j];
	for(i=0;i<n;i++)printf("%d\n",c[i]);
	return 0;
}


Measured memory_bytes: 2140
#include <iostream>
#include <vector>
using namespace std;
int main(void){

    int N, ans = 0;
    cin >> N;
    vector<int> d(N);
    
    for(int i = 0; i < N; i++){
        cin >> d[i];
    }
    
    for(int i = 0; i < N; i++){
        for(int j = i+1; j < N; j++){
            //cout << d[i] << " * " << d[j] << " = " << d[i] * d[j] << endl;
            ans += d[i] * d[j];
        }
            
    }
    
    cout << ans << endl;
}


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

using namespace std;

int main()
{
    int n;
    cin >> n;
    set<int> s;
    set<int>::iterator it;
    int x;
    for(int i =0; i < n; ++i) {
        cin >> x;
        s.insert(x);
    }

//    for(it = s.begin(); it != s.end(); ++it) {
     //   cout << *it;
  //  }

    cout << s.size();

    return 0;
}


Measured memory_bytes: 256
import qualified Data.Map as Map

main = do
    [h,w] <- map read.words <$> getLine
    contents <- lines <$> getContents

    let tizu = Map.fromList (zip [(i,j)| i <- [1..h], j <- [1..w]] (concat contents))
    let num_white = sum [1 | x <- (concat contents), x == '.']

    print $ points (h,w) tizu num_white [((1,1),1)] []


points (h,w) tizu num_white [] visited = -1
points (h,w) tizu num_white (((i,j),k):check) visited
    | or [i<1,i>h,j<1,j>w] = points (h,w) tizu num_white check visited
    | (i,j) == (h,w) = num_white - k
    | (i,j) `elem` visited = points (h,w) tizu num_white check visited
    | tizu Map.! (i,j) == '#' = points (h,w) tizu num_white check visited
    | otherwise = points (h,w) tizu num_white (check ++ [((i+1,j),k+1),((i-1,j),k+1),((i,j+1),k+1),((i,j-1),k+1)]) ((i,j):visited)

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

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

	std::vector<int> vx(n);
	for (int& k : vx) {
		std::cin >> k;
	}

	std::vector<int> vy(m);
	for (int& p : vy) {
		std::cin >> p;
	}

	vx.push_back(x);
	vy.push_back(y);

	std::sort(vx.begin(), vx.end());
	std::sort(vy.begin(), vy.end());



	//std::cout <<vx[n]<< std::endl;
	//std::cout << vy[0] << std::endl;


	///*
	if (vx[n]== vy[0] || vx[n] > vy[0]) {
		std::cout << "War" << std::endl;
		exit(0);
	}
	//*/



	std::cout <<"No War"<< std::endl;
	return 0;
}

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


int main(void) {
	int n, i, d[100003];
	
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> d[i];
	}

	sort(d, d + n);

	cout << d[n / 2] - d[n / 2 - 1] << endl;

	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(void)
{
    int i=0, s;
    scanf("%d", &s);
    if(s/100==0 && 1<=s%100 && s%100<=12){
        printf("YYMM\n");
    }
    else if(s/100>=13 && 1<=s%100 && s%100<=12){
        printf("YYMM\n");
    }
    else if(1<=s/100 && s/100<=12 && (s%100>=13 || s%100==0)){
        printf("MMYY\n");
    }
    else if(1<=s/100 && s/100<=12 && 1<=s%100 && s%100<=12){
        printf("AMBIGUOUS\n");
    }
    else{
        printf("NA\n");
    }
        
    return 0;
}


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

using namespace std;

int n, a[200][200], m, r, p[8], b, c, d, v[8], x = 1000000000, q[8];

void f(int y)
{
    if (y == r)
    {
        int s = 0;

        for (int i = 0; i < r-1; i++)
            s += a[p[i]][p[i+1]];

        x = min(x, s);
        return;
    }

    for (int i = 0; i < r; i++)
        if (!v[i])
        {
            v[i] = 1;
            p[y] = q[i];
            f(y+1);
            v[i] = 0;
        }
}

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

    for (int i = 0; i < r; i++)
    {
        cin >> q[i];
        q[i]--;
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j)
                a[i][j] = 1000000000;
            else
                a[i][j] = 0;

    for (int i = 0; i < m; i++)
    {
        cin >> b >> c >> d;
        a[b-1][c-1] = d;
        a[c-1][b-1] = d;
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                a[j][k] = min(a[j][k], a[j][i]+a[i][k]);

    f(0);
    cout << x;
}


Measured memory_bytes: 384
/********** Raaghav Raaj (cf: raaghavraaj, cc: mothercoder27) *************/
#include<bits/stdc++.h>
using namespace std;
#define fast cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#pragma optimize("-O3")

// #ifndef ONLINE_JUDGE
// #include "../Codechef/trace.h"
// #else
// #define trace(args...)
// #endif

#define int long long
#define double long double
#define vi vector<int>
#define vc vector<char>
#define pi pair<int, int>
#define pii pair<pi,int>
#define rep(i,a,b) for(int i=a; i<b; i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define sp " "
#define endl '\n'
#define all(v) v.begin(), v.end()
#define debug(data) for(auto it: data) cout<<it<<sp;
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

const int sz = 1e10;

int gcd(int n, int m) {
	return __gcd(n, m);
}

int power(int a, int b) {
	a %= sz;
	int res = 1;
	while (b) {
		if (b & 1) res = (res * a) % sz;
		a = (a * a) % sz;
		b >>= 1;
	}
	return res;
}

int modInverse(int a) { //sz must be prime
	return power(a, sz - 2);
}

void solve() {
	int n; cin >> n;

	int mon = 1000;

	vi a(n + 2);
	a[0] = INT_MAX;
	a[n + 1] = INT_MIN;
	rep(i, 0, n) cin >> a[i + 1];

	int s = 0;
	for (int i = 1; i <= n; i++)
	{
		if (i == 1)
		{
			if (a[i] <= a[i + 1])
			{
				s = mon / a[i];
				mon -= s * a[i];
			}
		}
		else if (i == n)
		{
			mon += s * a[i];
		}
		else
		{
			if (a[i] >= a[i - 1] && a[i] > a[i + 1])
			{
				mon += s * a[i];
				s = 0;
			}
			else if (a[i] < a[i - 1] && a[i] <= a[i + 1])
			{
				s = mon / a[i];
				mon -= s * a[i];
			}
		}

	}

	cout << mon << endl;

}

int32_t main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// 	freopen("tracefile.txt", "w", stderr);
// #endif
	fast;
	int T = 1;
	// cin >> T;
	rep(i, 1, T + 1) {
		// cout << "Case #" << i << ": " << endl;
		solve();
	}
}

Measured memory_bytes: 3648
N = int(input())
result = dict()

for _ in range(N):
    S = input()
    if S in result:
        result[S] += 1
    else:
        result[S] = 1

result = sorted(result.items(), key = lambda x:x[1])[::-1]
output, i, highest = [result[0][0]], 1, result[0][1]

if len(result) != 1:
    while result[i][1] == highest:
        output.append(result[i][0])
        i += 1
        if i == N:
            break

for name in sorted(output):
    print(name)


Measured memory_bytes: 43228
w_arr = Array.new() 
k_arr = Array.new()

10.times do
  w_arr.push(gets.to_i)
end

10.times do
  k_arr.push(gets.to_i)
end

puts "#{w_arr.sort.reverse[0..2].inject(:+)} #{k_arr.sort.reverse[0..2].inject(:+)}"

Measured memory_bytes: 8476
# Aizu Problem ALDS_1_1_B: Greatest Common Divisor
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def gcd(a, b):
    while b != 0:
       t = b
       b = a % b
       a = t
    return a

x, y = [int(_) for _ in input().split()]
print(gcd(x, y))

Measured memory_bytes: 7784
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<ll>adj[100005];
ll dp[100005];
bool vis[100005];
void dfs(ll n)
{
	vis[n]=1;
	for(ll i=0;i<adj[n].size();i++)
	{
		if(!vis[adj[n][i]])
			dfs(adj[n][i]);
			
		dp[n]=max(dp[n],1+dp[adj[n][i]]);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n,m,i,j;
	cin >> n >> m;
	for(i=0;i<m;i++)
	{
		ll x,y;
		cin >> x >> y;
		adj[x].push_back(y);
	}
	for(i=1;i<=n;i++)
	{
		if(!vis[i])
			dfs(i);	
	}
	ll ans=0;
	for(i=1;i<=n;i++)
		ans=max(dp[i],ans);
		
	cout<<ans<<"\n";
}

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

int main() {
  int a,b;
  string n;
  cin>>a>>n>>b;
  
  for(int i=0;i<a;i++){
    if(n.at(i)!=n.at(b-1)){
      n.at(i)='*';
    }
  }
  
  cout<<n<<endl;
}

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

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  string s; cin >> s;
  if (s == "zyxwvutsrqponmlkjihgfedcba") {
    cout << -1 << "\n";
    return 0;
  }
  int n = s.size();
  if (n < 26) {
    for (char c = 'a'; c <= 'z'; c++) {
      if (s.find(c) >= n) {
        s += c;
        cout << s << "\n";
        return 0;
      }
    }
  }
  char sc[n];
  for (int i = 0; i < n; i++) sc[i] = s[i]; 
  next_permutation(sc, sc + n);
  int m;
  for (int i = 0; i < n; i++) {
    if (s[i] != sc[i]) {
      m = i + 1;
      break;
    }
  }
  // bool memo[26]; memset(memo, 0, sizeof(memo));
  // for (int i = 24; i >= 0; i--) {
  //   if (s[i] < s[i + 1]) {
  //     s.resize(i + 1);
  //     for (int j = 0; j <= i; j++) memo[s[j] - 'a'] = 1;
  //     s[i] = 'a' + find(memo, memo + 26, 0) - memo;
  //     break;
  //   }
  // }
  for (int i = 0; i < m; i++) cout << sc[i];
  cout << "\n";
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;

namespace ABC170
{
    class D
    {
        static void Main(string[] args)
        {
            //var XN = Console.ReadLine().Split().Select(long.Parse).ToArray();
            //var input = Console.ReadLine();
            // var CA = Enumerable.Repeat(0, (int)N).Select(_ => Console.ReadLine().Split().Select(long.Parse).ToArray()).ToArray();
            //var AB = Console.ReadLine().Split().Select(long.Parse).ToArray();

            var N = long.Parse(Console.ReadLine());
            var A = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var Amax = A.Max();
            var Ans = new long[Amax + 10];
            for (int i = 0; i < A.Length; i++)
            {
                var index = 1;
                while (A[i] * index <= Amax)
                {
                    Ans[A[i] * index]++;
                    index++;
                }
            }

            var ans = 0;
            for (int i = 0; i < A.Length; i++)
            {
                if (Ans[A[i]] == 1) ans++;
            }

            Console.WriteLine(ans);
        }
    }
}

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

#define INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define Rep0(i, n)  for (int i=0; i<n; i++)

struct  Node {
    vector<vector<int>> T;
    bool fixed=false;
};

vector<vector<int>> Memo(65536, vector<int> (16, -1));

int F(const int &f, const int &fix, const int &t, vector<Node> &N, const int Step) {
    if (f==t) {
        if (Step==N.size())
            return 0;
        else
            return INF;
    }
    if (Memo.at(fix).at(f)>=0)
        return Memo.at(fix).at(f);
    N.at(f).fixed=true;
    int S=INF;
    Rep0(i, N.at(f).T.size()) {
        int tt=N.at(f).T.at(i).at(0);
        int dd=N.at(f).T.at(i).at(1);
        if (N.at(tt).fixed)
            continue;
        S=min(S, F(tt, fix|(1<<tt), 0, N, Step+1)+dd);
    }
    N.at(f).fixed=false;
    Memo.at(fix).at(f)=S;
    return S;
}

int main() {
    int V, E;
    cin >>V >>E;
    vector<Node> N(V);
    Rep0(i, E) {
        int s, t, d;
        cin >>s >>t >>d;
        N.at(s).T.push_back({t, d});
    }
    int S=INF;
    Rep0(i, N.at(0).T.size()) {
        int tt=N.at(0).T.at(i).at(0);
        int dd=N.at(0).T.at(i).at(1);
        int fix=1|(1<<tt);
        S=min(S, F(tt, fix, 0, N, 1)+dd);
    }
    if (S<INF)
        cout <<S <<endl;
    else
        cout <<-1 <<endl;
    return 0;
}



Measured memory_bytes: 9332
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


//SOLVE
void solve(void)
{
  int D,N; cin>>D; cin>>N;
  if(D == 0)
  {
    if(N != 100)
    {
      cout<<N<<endl;
    }
    else
    {
      cout<<101<<endl;
    }
    
  }
  else if (D == 1)
  {
    int index = 0;
    int X = 0;
    while(index != N)
    {
      X += 100;
      if(X%10000 == 0)continue;
      index++;
    }
    cout<<X<<endl;
    
  }
  else
  {
    if(N == 100)N++;
    cout<<10000*N<<endl;
  }
  

  return;
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
  int X, Y, Z, K;
  cin >> X >> Y >> Z >> K;
  long long A[X], B[Y], C[Z];
  REP(i, X) cin >> A[i];
  REP(i, Y) cin >> B[i];
  REP(i, Z) cin >> C[i];
  sort(A, A+X);
  sort(B, B+Y);
  sort(C, C+Z);

  priority_queue<pair<long long, tuple<int, int, int>>> q;
  q.push(make_pair(A[X-1]+B[Y-1]+C[Z-1], make_tuple(X-1, Y-1, Z-1)));

  pair<long long, tuple<int, int, int>> pr;
  int cursol_A;
  int cursol_B;
  int cursol_C;
  set<tuple<int, int, int>> seen;

  REP(i, K) {
    while (true) {
      pair<long long, tuple<int, int, int>> pr = q.top(); q.pop();
      // cout << pr.first << endl;
      // cout << 1 << endl;
      int& cursol_A = get<0>(pr.second);
      int& cursol_B = get<1>(pr.second);
      int& cursol_C = get<2>(pr.second);
      // cout << cursol_A << endl;
      if (seen.count(make_tuple(cursol_A, cursol_B, cursol_C)) == 0) {
        cout << pr.first << endl;
    // cout << 1 << endl;
    seen.insert(make_tuple(cursol_A, cursol_B, cursol_C));
    // cout << 1 << endl;

    if(cursol_A >= 1) q.push(make_pair((A[cursol_A-1] + B[cursol_B] + C[cursol_C]), make_tuple(cursol_A-1, cursol_B, cursol_C)));
    if(cursol_B >= 1) q.push(make_pair((A[cursol_A] + B[cursol_B-1] + C[cursol_C]), make_tuple(cursol_A, cursol_B-1, cursol_C)));
    if(cursol_C >= 1) q.push(make_pair((A[cursol_A] + B[cursol_B] + C[cursol_C-1]), make_tuple(cursol_A, cursol_B, cursol_C-1)));
    break;

      }
    }
    
    


  }
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

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


using namespace std;

int main (void){
    
    int a[500] = {0};
    int b[500] = {0};
    int i= 0,j = 0,k = 0,l = 0;
    int answer[1000][2] = {0};
    
    while(cin >> a[i++] >> a[i++] >> a[i++] >> a[i++])
    {
        cin >> b[j++] >> b[j++] >> b[j++] >> b[j++];
        
        FOR(m,i-4,i)
            if(a[m] == b[m])
                answer[l][0]++;
        FOR(m,i-4,i)
            FOR(k,i-4,i)
                if(a[m] == b[k] && m != k)
                    answer[l][1]++;
        l++;
    }
    REP(m,l)
    cout << answer[m][0] << " " << answer[m][1] << endl;
    return 0;
}

Measured memory_bytes: 1168
N, Q = (int(i) for i in input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]

accum = [0] * N

def countAC():
    count = 0
    for i in range(1, N):
        if(S[i-1] == "A" and S[i] == "C"):
            count += 1
        accum[i] = count



countAC()

for i in range(Q):
    print(accum[LR[i][1]-1] - accum[LR[i][0]-1])


Measured memory_bytes: 30660
INF = 1000000000
read(T) = parse(T, readline())
reads(T) = map(x->parse(T,x),split(readline()))

function main()
    n = read(Int)
    v = reads(Int)
    dp = [INF for i in 1:n]
    dp[1] = 0
    for i in 1:n-1
        if (i + 1 <= n) dp[i+1] = min(dp[i+1], dp[i] + abs(v[i] - v[i+1])) end
        if (i + 2 <= n) dp[i+2] = min(dp[i+2], dp[i] + abs(v[i] - v[i+2])) end
    end
    println(dp[n])
end

@inbounds main()


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

#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int, int>>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int, int>
#define int long long int
#define inf INT_MAX
#define _inf INT_MIN
#define whilet int t;cin>>t;while(t--)
const int N = 100005;
const int mod = 1e9 + 7;

vi stones(N);

void recur(int n, int k) {

	int dp[N];
	memset(dp, -1, sizeof(dp));

	dp[0] = 0;

	for (int i = 1; i <= k; i++) {
		bool flag = false;
		for (int j = 0; j < n; j++) {
			if (i - stones[j] >= 0 ) {
				if (dp[i - stones[j]] == 0 ) {flag = true; break;}
			}
		}

		if (flag) dp[i] = 1;
		else dp[i] = 0 ;
	}

	if (dp[k] == 1 ) cout << "First" << endl;
	else cout << "Second" << endl;

}


void solve() {

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) cin >> stones[i];

	recur(n , k );
}

void init() {
	ios_base:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("../input.txt", "r", stdin);
	freopen("../output.txt", "w", stdout);
#endif
}


int32_t main()
{
	init();
	// whilet solve();
	solve();
}

Measured memory_bytes: 4780
'use strict'

const main = (input) => {
    input = input.split('\n').map(v => parseInt(v))
    const N = input[0]
    const K = input[1]
    let current = 1
    for(let i = 1; i <= N; i++){
        let add = Math.min(K, current) 
        current += add
    }
    console.log(current)
}

main(require('fs').readFileSync('/dev/stdin', 'utf-8'))

Measured memory_bytes: 21064