stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

#include <cstring>

#include <string>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <utility>

#include <map>

#include <stack>

#include <set>

#include <vector>

#include <queue>

#include <deque>

#include <sstream>

#define x first

#define y second

#define mp make_pair

#define pb push_back

#define LL long long

#define LB long double

#define Pair pair<int,int>

#define LOWBIT(x) x & (-x)

using namespace std;



const int MOD=1e9+7;

const double eps=1e-10;

const int INF=2e9;

const LL LINF=2e16;

const int magic=100;



inline int getint()

{

	char ch;

	while ((ch=getchar())<'0' || ch>'9') {}

	int res=ch-'0';

	while ((ch=getchar())>='0' && ch<='9') res=res*10+ch-'0';

	return res;

}



int n,e,T;

LL a[100048];

priority_queue<pair<LL,int> > q1,q2;

LL dp[100048];



int main ()

{

	int i;

	n=getint();e=getint();T=getint();

	for (i=1;i<=n;i++) a[i]=(LL)getint();

	dp[0]=0;

	a[0]=0;

	q2.push(mp(a[0]-dp[0],0));

	//dp[1]=a[1]+T;

	//q2.push(mp(a[1]-dp[1],1));

	int num1,num2;

	for (i=1;i<=n;i++)

	{

		

		bool f=true;

		while (!q2.empty() && f)

		{

			int num=q2.top().y;f=false;

			if (T-2*a[i]+2*a[num+1]<0)

			{

				q2.pop();f=true;

				q1.push(mp(a[num]+2*a[num+1]-dp[num],num));

			}

		}

		LL ans1=LINF,ans2=LINF;

		if (!q1.empty())

		{

			num1=q1.top().y;

			ans1=dp[num1]+3*a[i]-a[num1]-2*a[num1+1];

		}

		if (!q2.empty())

		{

			num2=q2.top().y;

			ans2=dp[num2]+a[i]-a[num2]+T;

		}

		dp[i]=min(ans1,ans2);

		q2.push(mp(a[i]-dp[i],i));

	}

	//for (i=1;i<=n;i++) cout<<dp[i]<<' ';

	//cout<<endl;

	cout<<dp[n]+(e-a[n])<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

    //freopen("computer.in","r",stdin);

    //freopen("computer.out","w",stdout);

    scanf("%d%d%d",&n,&m,&T);

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

        scanf("%lld",&a[i]);

        d[i]=INF;

    }

    if(n<=1000){

        for(int i=1;i<=n;i++)

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

                d[i]=min(d[i],d[j]+a[i]-a[j]+f+max(a[i]-a[j+1],T-f));

            }

        ll ans=d[n]+m-a[n];

        printf("%lld\n",ans);

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

        printf("%lld\n",ans);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <fstream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <utility>

#include <map>

#include <set>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <functional>

#include <sstream>

#include <cstring>

#include <bitset>

#include <stack>

using namespace std;

#define MP make_pair

#define PB push_back

const int INF=1e9;



int n,e,t,pos;

long long a[100005];

long long dp[100005],cur;



int main()

{

	cin>>n>>e>>t;

	for (int i=1;i<=n;i++) cin>>a[i];

	dp[0]=0;

	cur=1e18;

	pos=0;

	for (int i=1;i<=n;i++)

	{

		while (t<=2*(a[i]-a[pos+1]))

		{

			cur=min(cur,dp[pos]-2*a[pos+1]);

			pos++;

		}

		dp[i]=min(cur+2*a[i],dp[pos]+t);

	}

	cout<<dp[n]+e;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

    //freopen("computer.in","r",stdin);

    //freopen("computer.out","w",stdout);

    scanf("%d%d%d",&n,&m,&T);

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

        scanf("%lld",&a[i]);

        d[i]=INF;

    }

    if(n<=1000){

        for(int i=1;i<=n;i++)

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

                d[i]=min(d[i],d[j]+a[i]-a[j]+f+max(a[i]-a[j+1],T-f));

            }

        ll ans=d[n]+m-a[n];

        printf("%lld\n",ans);

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

        printf("%lld\n",ans);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
/* --- author: dxm --- */

#include<bits/stdc++.h>

using namespace std;



#define ll long long

#define INF 2147483647

#define Inf 1e18

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

#define REP(i,n) for(int (i)=1;(i)<=n;i++)

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

inline void Fail(){

	printf("0");

	exit(0);

}



const int maxn=100005;

int n,e,t;

ll dp[maxn];

int x[maxn],y[maxn];

class segtree{

public:

	ll tree[maxn*4];

	int leaf[maxn];

	void build(int l,int r,int node){

		if(l==r){

			leaf[l]=node;

			tree[node]=Inf;

			return;

		}

		int mid=(l+r)>>1;

		build(l,mid,node*2);

		build(mid+1,r,node*2+1); 

		tree[node]=min(tree[node*2],tree[node*2+1]);

	}

	void upd(int node,ll val){

		node=leaf[node];

		tree[node]=val;

		node>>=1;

		while(node){

			tree[node]=min(tree[node*2],tree[node*2+1]);

			node>>=1;

		}

	}

	ll query(int l,int r,int vl,int vr,int node){

		if(r<l||vr<vl)return Inf;

		if(l>vr||r<vl)return Inf;

		if(l>=vl&&r<=vr)return tree[node];

		int mid=(l+r)>>1;

		return min(query(l,mid,vl,vr,node*2),query(mid+1,r,vl,vr,node*2+1));

	}

}t1,t2;



int main(){

	scanf("%d%d%d",&n,&e,&t);

	rep(i,n)scanf("%d",&x[i]),y[i]=2*x[i];

	t1.build(0,n-1,1);

	t2.build(0,n-1,1);

	rep(i,n){

		dp[i]=max((x[i]-x[0])*2LL,1LL*t);

		int pos=lower_bound(y,y+n,2*x[i]-t)-y;

		dp[i]=min(dp[i],min(t1.query(0,n-1,0,pos-2,1)+2LL*x[i],t2.query(0,n-1,max(pos-1,0),n-1,1)+t));

		t1.upd(i,dp[i]-2LL*x[i+1]);

		t2.upd(i,dp[i]);

	}

	printf("%lld",e+dp[n-1]);

	return 0;

}



/*

Input:

-----------------

Output:

*/

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

#define INF 2100000006

#define MAXN 100006

using namespace std;

long long m,T,minone,a[MAXN],d[MAXN];

int n,l[MAXN],last;

int find(int x)

{

	int l=1,r=x;

	while(l<r)

	{

		int mid=(l+r)/2;

		if(T-2*(a[x]-a[mid])>0) r=mid;

		else l=mid+1;

	}

	return l;

}

int main()

{

	//freopen("computer.in","r",stdin);

	//freopen("computer.out","w",stdout);

	scanf("%d%lld%lld",&n,&m,&T);

	for(int i=1;i<=n;i++)

		scanf("%lld",&a[i]);

	for(int i=1;i<=n;i++)

		l[i]=find(i);

	minone=INF;

	for(int i=1;i<=n;i++)

	{

		while(last<l[i]-1)

		{

			last++;

			minone=min(minone,d[last-1]-a[last-1]-2*a[last]);

		}

		long long len=a[i]-a[l[i]];

		d[i]=d[l[i]-1]+a[l[i]]-a[l[i]-1]+len+T;

		d[i]=min(d[i],minone+3*a[i]);

	}

	printf("%lld",d[n]+m-a[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define FOR(i,a,b) for(int i = (a); i < (b); i++)

#define RFOR(i,b,a) for(int i = (b)-1; i >= (a); i--)

#define ITER(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<LL> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL) INF;



const int MAX = 100100;



int A[MAX];

LL A2[MAX];



LL D[MAX];



VI ADD[MAX];

VI REM[MAX];



LL ST[MAX];



multiset<LL> S;



int main()

{

	//freopen("in.txt", "r", stdin);

	//ios::sync_with_stdio(false); cin.tie(0);



	int n, e, t;

	scanf("%d%d%d", &n, &e, &t);

	FOR (i, 0, n)

	{

		scanf("%d", &A[i]);

		A2[i] = A[i] * 2;

	}



	FOR (i, 0, n + 7)

	{

		ST[i] = LINF;

	}





	LL res = e;



	D[0] = 0;

	LL mn = LINF;



	FOR (i, 0, n + 1)

	{

		FOR (j, 0, SZ(ADD[i]))

		{

			S.insert(ADD[i][j]);

		}



		FOR (j, 0, SZ(REM[i]))

		{

			S.erase(S.find(REM[i][j]));

		}



		mn = min(mn, ST[i]);



		if (i == 0) D[i] = 0;

		else

		{

			D[i] = LINF;

			if (SZ(S))D[i] = *S.begin();



			D[i] = min(D[i], 2 * A[i - 1] + mn);



	//		cout<<i<<' '<<mn<<endl;

	//		if (SZ(S)) cout<<"** "<<*S.begin()<<endl;



			if (i == n) break;

		}



		int pos = upper_bound(A2, A2 + n, A2[i] + t) - A2;



	//	cout<<i<<": "<<pos<<endl;



		ADD[i+1].PB(D[i] + t);

		REM[pos + 1].PB(D[i] + t);



		ST[pos + 1] = min(ST[pos + 1], D[i] - 2 * A[i]);

		//mn = min(mn, D[i] - 2 * A[i]);

	}





/*	FOR (i, 0, n + 1)

	{

		cout<<D[i]<<' ';

	}

	cout<<endl;*/



	res += D[n];



	cout<<res<<endl;





}






// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

#define INF 2100000006

#define MAXN 100006

using namespace std;

long long m,T,minone,a[MAXN],d[MAXN];

int n,l[MAXN],last;

int find(int x)

{

	int l=1,r=x;

	while(l<r)

	{

		int mid=(l+r)/2;

		if(T-2*(a[x]-a[mid])>0) r=mid;

		else l=mid+1;

	}

	return l;

}

int main()

{

	//freopen("computer.in","r",stdin);

	//freopen("computer.out","w",stdout);

	scanf("%d%lld%lld",&n,&m,&T);

	for(int i=1;i<=n;i++)

		scanf("%lld",&a[i]);

	for(int i=1;i<=n;i++)

		l[i]=find(i);

	minone=INF;

	for(int i=1;i<=n;i++)

	{

		while(last<l[i]-1)

		{

			last++;

			minone=min(minone,d[last-1]-a[last-1]-2*a[last]);

		}

		long long len=a[i]-a[l[i]];

		d[i]=d[l[i]-1]+a[l[i]]-a[l[i]-1]+len+T;

		d[i]=min(d[i],minone+3*a[i]);

	}

	printf("%lld",d[n]+m-a[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



#define int long long

typedef vector<int>vint;

typedef pair<int,int>pint;

typedef vector<pint>vpint;

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

#define reps(i,f,n) for(int i=(f);i<(n);i++)

#define all(v) (v).begin(),(v).end()

#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define pb push_back

#define fi first

#define se second

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

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



const int INF=1001001001001001001ll;

struct segtree{

    static const int SEG=1<<17;

    vint dat;

    segtree():dat(SEG*2){}

    void update(int k,int x){

        k+=SEG-1;

        dat[k]=x;

        while(k){

            k=(k-1)/2;

            dat[k]=min(dat[k*2+1],dat[k*2+2]);

        }

    }

    int query(int a,int b,int k=0,int l=0,int r=SEG){

        if(r<=a||b<=l)return INF;

        if(a<=l&&r<=b)return dat[k];

        return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));

    }

};



int N,E,T;

int X[111111];

int dp[111111];

signed main(){

    cin>>N>>E>>T;

    X[0]=0;

    for(int i=1;i<=N;i++)cin>>X[i];



    segtree segA;

    segtree segB;

    segA.update(0,-2*X[1]);

    segB.update(0,0);

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

        int lb=-1,ub=i;

        while(ub-lb>1){

            int mid=(ub+lb)/2;

            if(2*(X[i]-X[mid+1])<T)ub=mid;

            else lb=mid;

        }

        int val=INF;

        if(ub)val=segA.query(0,ub)+3*X[i];

        if(ub!=i)chmin(val,segB.query(ub,i)+T+X[i]);

        dp[i]=val;

        segA.update(i,val-X[i]-2*X[i+1]);

        segB.update(i,val-X[i]);

    }

    cout<<dp[N]+E-X[N]<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



#define int long long



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

#define pb push_back

#define all(v) (v).begin(),(v).end()

#define fi first

#define se second

typedef vector<int>vint;

typedef pair<int,int>pint;

typedef vector<pint>vpint;



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

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



const int INF=1001001001001001001ll;



int N,E,T;

int X[111111];

int dp[111111];



signed main(){

    cin>>N>>E>>T;

    rep(i,N)cin>>X[i+1];



    int ei=INF;

    int L=1;

    deque<pint>deq;

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

        int tmp=dp[i-1]+X[i]-X[i-1];

        while(deq.size()&&deq.back().fi>T+tmp-X[i])deq.pop_back();

        deq.push_back({T+tmp-X[i],i});

        while((X[i]-X[L])*2>T){

            chmin(ei,dp[L-1]+X[L]-X[L-1]-3*X[L]);

            if(deq.front().se==L)deq.pop_front();

            L++;

        }



        dp[i]=min(deq.front().fi+X[i],ei+3*X[i]);

    }



    cout<<dp[N]+E-X[N]<<endl;

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define fo(i,a,b) for(int i=a;i<=b;i++)

#define fod(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long ll;

const int N=1e5+10,inf=(1<<30);

ll f[N],p[N];int n,e,t;

int main()

{

	scanf("%d%d%d",&n,&e,&t);

	fo(i,1,n) scanf("%lld",&p[i]);

	memset(f,63,sizeof(f));f[0]=0;

	ll mn=inf;

	for(int i=1,j=0;i<=n;i++) {

		for(;t<=(p[i]-p[j+1])<<1;j++)

			mn=min(mn,f[j]-2*p[j+1]);

			if(j<i) f[i]=min(f[i],f[j]+t);

			f[i]=min(f[i],mn+2*p[i]);

	}

	printf("%lld\n",f[n]+e);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

typedef long long LL;

const int MAXN = 100000+10;

const int INF = 0x3f3f3f3f;

int n, t, e;

LL x[MAXN], f[MAXN];

int main(){

   // freopen("t.in", "r", stdin);

    scanf("%d%d%d", &n, &e, &t);

    for(int i=1; i<=n; ++i) scanf("%lld", &x[i]);

    int j=0;

    LL mn = 1e14;

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

        while((x[i]-x[j+1])*2>=t){

            mn = std::min(mn, f[j] - 2*x[j+1]);

            j++;

        }

        f[i] = std::min(f[j]+t, mn + 2*x[i]);

    }

    printf("%lld\n", f[n]+e);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define fo(i,a,b) for(int i=a;i<=b;i++)

#define fod(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long ll;

const int N=1e5+10,inf=(1<<30);

ll f[N],p[N];int n,e,t;

int main()

{

    scanf("%d%d%d",&n,&e,&t);

    fo(i,1,n) scanf("%lld",&p[i]);

    memset(f,63,sizeof(f));f[0]=0;

    ll mn=inf;

    for(int i=1,j=0;i<=n;i++) {

        for(;t<=(p[i]-p[j+1])<<1;j++)

            mn=min(mn,f[j]-2*p[j+1]);

            if(j<i) f[i]=min(f[i],f[j]+t);

            f[i]=min(f[i],mn+2*p[i]);

    }

    printf("%lld\n",f[n]+e);

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<iostream>

#include<cstring>

#define RG register

#define LL long long

using namespace std;

const int N=1e5+10;

int n;

LL e,t,x[N],dp[N],tt=1e18;

template<typename I> inline void read(I &ot){

	I ch=getchar(), x=0, f=1;

	while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();	}

	while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();	}

	ot=x*f;}

template<typename I, typename... U> inline void read(I &x,U&... y){read(x); read(y...);}

template<typename I>inline I mi(const I&a,const I&b){return a<b ? a : b;}

int main()

{

//	freopen("Shik and Game.in","r",stdin);

	//freopen(".out","w",stdout);

	read(n,e,t);

	for(int i=1;i<=n;i++) read(x[i]), dp[i]=2e9;

	for(int i=1,j=0;i<=n;i++)

	{

		while(2*(x[i]-x[j+1])>=t) 

		{

			tt=mi(tt,dp[j]-2*x[j+1]);

			j++;

		}

		dp[i]=mi(dp[j]+t,tt+2*x[i]);

	}

	printf("%lld\n",dp[n]+e);

	//fclose(stdin); fclose(stdout);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <stdio.h>

#include <string.h>

#define INF 1000001



int main(void){

	int i, j, n ,c, small1, small2;

	int dp1[1000000],dp2[1000000];

	scanf("%d",&n);

	while(n != 0){

		for(i = 0;i <= n;i++)

			dp1[i] = dp2[i] = INF;

		dp1[0] = dp2[0] = 0;

		for(i = 0;i < n;i++){

			small1 = dp1[n];

			if(small1 > dp1[i] + 1 && dp1[i] != INF){

				for(j = 1,c = j * (j + 1) * (j + 2);c / 6 + i <= n;j++,c = j * (j + 1) * (j + 2)){

					if(dp1[c / 6 + i] > dp1[i] + 1 && dp1[i] != INF){

						dp1[c / 6 + i] = dp1[i] + 1;

					}

				}

			}

		}

		for(i = 0;i < n;i++){

			small2 = dp2[n];

			if(small2 > dp2[i] + 1 && dp2[i] != INF){

				for(j = 1,c = j * (j + 1) * (j + 2);c / 6 + i <= n;j++,c = j * (j + 1) * (j + 2)){

					if(dp2[c / 6 + i] > dp2[i] + 1 && (c / 6) % 2 == 1 && dp2[i] != INF)

						dp2[c / 6 + i] = dp2[i] + 1;

				}

			}

		}

		printf("%d %d\n",dp1[n],dp2[n]);

		scanf("%d",&n);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <stdlib.h>



int n;



void solve(int *min,int flag,int c){

	int i;

	static int sum = 0, count = 0;

	if(count + 1 < *min && sum < n){

		for(i = 0;((i + 1) * (i + 2) * (i + 3)) / 6 + sum <= n && i < c;i++);

		while(i > 0){

			if(flag == 1 && i * (i + 1) * (i + 2) / 6 % 2 == 0){

				i--;

				continue;

			}

			sum += i * (i + 1) * (i + 2) / 6;

			count++;

			solve(min,flag,i);

			sum -= i * (i + 1) * (i + 2) / 6;

			count--;

			i--;

		}

	}

	else if(sum == n){

		if(count < *min)

			*min = count;

	}

	return;

}



int main(void){

	int min;

	scanf("%d",&n);

	while(n != 0){

		min = n;

		solve(&min,0,0x7FFFFFFF);

		printf("%d ",min);

		min = n;

		solve(&min,1,0x7FFFFFFF);

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

		scanf("%d",&n);

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#define N 1000000



int all[N+1],odd[N+1];

int pollock[1000];

int num;



int BackTrack(int n,int type){

  int i,tmp,ans = N+1;

  if(type && odd[n]<=N)return odd[n];

  if(!type && all[n]<=N)return all[n];

  //if(n==0)return 0;



  for(i=num-1;i>=0;i--){

    //printf("%d\n",pollock[i]);

    if(pollock[i]>n)continue;

    if(type && !(pollock[i]&1) )continue;

    tmp = BackTrack(n-pollock[i],type);

    if(ans > tmp+1)ans = tmp+1;

  }



  if(type)odd[n] = ans;

  if(!type)all[n] = ans;

  return ans;

}



int main(){

  int i,n,tmp;



  for(i=0;i<=N;i++)all[i] = odd[i] = N+1;

  all[0] = odd[0] = 0;



  for(num=1;;num++){

    tmp = num*(num+1)*(num+2)/6;

    if(tmp>N)break;

    pollock[num-1] = tmp;

  }

  num--;

  while(scanf("%d",&n) && n){

    printf("%d %d\n",BackTrack(n,0),BackTrack(n,1));

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>



using namespace std;



int m;

int f(int n) { return n*(n+1)*(n+2)/6; }

vector<int> l1, l2;



void r(int n, int step, vector<int> &l, int p) {

  if(step+1 >= m) return;

 

  for(int i=p; i>=0; i--) {

    int n2 = n-l[i];

    if(n2<0) continue;

    if(n2==0) {

      m = step+1;

      return;

    }

    if(n2>0) {

      r(n2, step+1, l, i);

    }

  }

  

}



int main() {

  while(1) {

    vector<int> l1, l2;

    int n;



     cin >> n;

     if(n==0) break;

    

    // not over

    for(int i=1; true; i++) {

      int mm = f(i);

      if(mm>n) break;

      l1.push_back(mm);

      if(mm&1) l2.push_back(mm);

    }



    m = n;

    r(n, 0, l1, l1.size()-1);

    cout << m;



    cout << ' ';

    

    m = n;

    r(n, 0, l2, l2.size()-1);

    cout << m;



    cout << "\n";



    

  }

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

using namespace std;



int main()

{

    long long n, m;

    cin >> n >> m;

    if(n == 2 || m == 2) cout << 0;

    else if(min(n, m) == 1){

        int maximum = max(n, m);

        cout << (maximum == 1 ? 1 : maximum - 2);

    } else 

        cout << (m-2)*(n-2);

    

    return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

using namespace std;



int main()

{

    long long n, m;

    scanf("%lld %lld", &n, &m);

    if(n == 2 || m == 2) printf("0");

    else if(min(n, m) == 1){

        int maximum = max(n, m);

        printf("%lld", maximum == 1 ? 1 : maximum - 2);

    } else 

        printf("%lld", (m-2)*(n-2));

    

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

using namespace std;



int main()

{

    long long n, m, down = 0;

    cin >> n >> m;

    if (n > m)

    {

        swap(n, m);

    }

    if (n == 1)

    {

        if (m == 1)

        {

            down = 1;

        }

        else

        {

            down = m - 2;

        }

    }

    else

    {

        down = (n - 2) * (m - 2);

    }

    cout << down;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#define ll long long

#define fup(i,a,b) for(int i=a;i<=b;++i)



void Main()

{

    ll n,m;

    scanf("%lld%lld",&n,&m);

    ll s;

    if(n>1&&m>1)s=m+m+n+n-4;

    else if(m==1&&n==1)s=0;

    else s=2;

    printf("%lld",n*m-s);

}

int main()

{

Main();

return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define ll long long

vector <ll > v;

string st1 ,st2,st3;

ll a,b,cnt,degit;







int  main()

{

    cin>>a>>b;



    cout<<abs(a*b-((a*2)+(b*2)-4));

}












// Optimized solution to the same problem (faster):
#include<stdio.h>

#define ll long long

#define fup(i,a,b) for(int i=a;i<=b;++i)



void Main()

{

    ll n,m;

    scanf("%lld%lld",&n,&m);

    ll s;

    if(n>1&&m>1)s=m+m+n+n-4;

    else if(m==1&&n==1)s=0;

    else s=2;

    printf("%lld",n*m-s);

}

int main()

{

Main();

return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n,re,sum;

    cin>>n;

    re=n;

    sum=0;

    while(re>0)

    {

        sum+=re%10;

        re/=10;

    }

    if(n%sum==0)

    {

        printf("Yes\n");

        //printf("S")

    }

    else printf("No\n");

    return  0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>



int main()

{

	long long int n, num, sum = 0;

	scanf("%lld", &n);

	

	num = n;

	while(num != 0)

	{

		sum += num % 10;

		num /= 10;

	}

	

	if(n % sum == 0) printf("Yes\n");

	else printf("No\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

const int maxn = 1e6+10;

int m,n;

int main()

{

	cin>>n;

	int j=n;

	long long ans=0;

	while(n)

	{

		ans+=n%10;

		n/=10;

	}

	if(j%ans==0) cout<<"Yes";

	else cout<<"No";

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>



int main()

{

	long long int n, num, sum = 0;

	scanf("%lld", &n);

	

	num = n;

	while(num != 0)

	{

		sum += num % 10;

		num /= 10;

	}

	

	if(n % sum == 0) printf("Yes\n");

	else printf("No\n");

}

// Fastest known solution for this problem: