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

using namespace std;

typedef long long ll;

const ll inf=1ll<<50;

typedef pair<ll,ll> ii;

const int N=4e3+20;

ll d[N],n,m;

vector<ii> e[N];

bool neg[N];

void calc()

{

    fill(d,d+1+n,inf);

    memset(neg,false,sizeof(neg));

    d[1]=0;

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

    {

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

        {

            for(int j=0;j<e[i].size();j++)

            {

                ll v=e[i][j].first,w=e[i][j].second;

                if(d[i]==inf)

                    continue;

                if(d[v]>d[i]+w)

                    d[v]=d[i]+w;

            }

        }

    }





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

    {

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

        {

            for(int j=0;j<e[i].size();j++)

            {

                ll v=e[i][j].first,w=e[i][j].second;

                if(d[i]==inf)

                    continue;

                if(d[v]>d[i]+w)

                {

                    d[v]=d[i]+w;

                    neg[v]=true;

                }

                if(neg[i]==true)

                    neg[v]=true;

            }

        }

    }

    if(neg[n]==false)

        cout<<-d[n]<<endl;

    else

        puts("inf");



}

int main()

{

    while(cin>>n>>m)

    {

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

            e[i].clear();

        ll u,v,w;

        while(m--)

        {

            cin>>u>>v>>w;

            e[u].push_back(ii(v,-w));

        }

        calc();

    }

    return 0;

}


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

using namespace std;

using ll = long long;

const ll INF = 1LL << 50;



const int N = 1000 + 10;



int a[N*2], b[N*2];

ll c[N*2];

int main(void)

{

    int n, m;

    cin >> n >> m;

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

    {

        cin >> a[i] >> b[i] >> c[i];

        c[i] = -c[i];

    }



    ll dist[N];

    bool negative[N];

    memset(dist, 0x3f, sizeof dist);

    memset(negative, 0, sizeof negative);

    dist[1] = 0;



    for (int loop = 0; loop < n - 1; ++ loop)

    {

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

        {

            if (dist[b[i]] > dist[a[i]] + c[i])

            {

                dist[b[i]] = dist[a[i]] + c[i];

            }

        }

    }



    ll ans = dist[n];

    for (int loop = 0; loop < n ; ++ loop)

    {

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

        {



            if (dist[b[i]] > dist[a[i]] + c[i])

            {

                dist[b[i]] = dist[a[i]] + c[i];

                negative[b[i]] = true;

            }



            if (negative[a[i]] == true)

            {

                negative[b[i]] = true;

            }

        }

    }

    if (negative[n])

        cout << "inf" << endl;

    else

        cout << -ans << endl;

    return 0;

}


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

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

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

#define INF (1e15)



using namespace std;



typedef long long ll;

typedef pair<int, int> P;



const int MAX_N = 1000;

const int MAX_M = 2000;



int a[MAX_M], b[MAX_M];

ll c[MAX_M];

ll dist[MAX_N];



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	int N, M; cin >> N >> M;



	rep (i, M){

		cin >> a[i] >> b[i] >> c[i];

		--a[i], --b[i];

	} // end rep



	rep (i, N){

		dist[i] = -INF;

	} // end rep



	dist[0] = 0LL;

	rep (update, 5 * MAX_N){

		rep (i, M){

			if (dist[b[i]] < dist[a[i]] + c[i]){

				dist[b[i]] = dist[a[i]] + c[i];

			} // end if

		} // end rep

	} // end rep



	ll ans = dist[N - 1];



	rep (update, 5 * MAX_N){

		rep (i, M){

			if (dist[b[i]] < dist[a[i]] + c[i]){

				dist[b[i]] = dist[a[i]] + c[i];

			} // end if

		} // end rep

	} // end rep



	if (ans != dist[N - 1]){

		cout << "inf" << endl;

	}else{

		cout << ans << endl;

	} // end if



	return 0;

}

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

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

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

#define INF ((ll)(1e15))



using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef pair<int, ll> IL;



const int MAX_N = 1000;

vector<IL> G[MAX_N]; // P(to,cost)



ll dist[MAX_N];



int main()

{

	rep (i, MAX_N) G[i].clear();

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	

	int N, M; cin >> N >> M;

	rep (i, M){

		int a, b; ll c; cin >> a >> b >> c;

		--a, --b;

		G[a].push_back(IL(b,-c));

	} // end rep



	rep (i, N){

		dist[i] = INF;

	} // end rep



	bool negative = false;

	dist[0] = 0LL;

	rep (iter, 2 * N){

		rep (v, N){

 			if (dist[v] == INF) continue;

			for (int j = 0; j < (int)G[v].size(); ++j){

				int u = G[v][j].first;

				ll c = G[v][j].second;

				if (dist[u] > dist[v] + c){

					dist[u] = dist[v] + c;

					if (u == N - 1 && iter >= N){

						negative |= true;

					} // end if

				} // end if

			} // end for

		} // end rep

	} // end rep



	if (!negative){

		cout << -dist[N - 1] << endl;

	}else{

		cout << "inf" << endl;

	} // end if



	return 0;

}

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

using namespace std;



using ll = long long;

const ll INF = 1LL << 50;





 int main(void) {

 int N, M;

 cin >> N >> M;



 const int NMAX = 1000;

 const int MMAX = 2000;

 int a[MMAX], b[MMAX];

 ll c[MMAX];



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

 cin >> a[i] >> b[i] >> c[i];

 c[i] = -c[i];

 }



 ll dist[NMAX];



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

 dist[i] = INF;

 }



 dist[0] = 0;





for (int loop = 0; loop < N - 1; ++ loop) {

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



 if (dist[a[i] - 1] == INF) continue;



 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {

 dist[b[i] - 1] = dist[a[i] - 1] + c[i];

 }

 }

 }



 ll ans = dist[N - 1];





 bool negative[NMAX];



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

 negative[i] = false;

 }



 for (int loop = 0; loop < N ; ++ loop) {

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

 if (dist[a[i] - 1] == INF) continue;



 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {

 dist[b[i] - 1] = dist[a[i] - 1] + c[i];

 negative[b[i] - 1] = true;

 }



 if (negative[a[i] - 1] == true) {

 negative[b[i] - 1] = true;

 }

 }

 }





 if (negative[N - 1])

 cout << "inf" << endl;

 else

 cout << -ans << endl;



 return 0;

 }


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

#include <cstdlib>

#include <vector>



using namespace std;



struct edge {

	int from;

	int to;

	long long cost;

};

edge es[2000];

long long d[1000];

int num[1000];

int N,M;



long long INF = 1LL << 50;



bool shortest_path(int s);

//bool find_n_loop();



int main(){



	scanf("%d %d",&N,&M);



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

		int a,b;

		long long c;

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

		struct edge e;

		e.from = a-1;

		e.to = b-1;

		e.cost = -1*c;

		es[i] = e;

	}





	if(shortest_path(0)){

		printf("inf\n");

	}else{

		//printf("%d\n",num[N-1]);



		printf("%lld\n",-d[N-1]);

	}

	/*

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

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

	}

	*/



	return 0;

}



//

bool shortest_path(int s){

	for(int i=0;i<N;i++) d[i] = INF;

	d[s] = 0;

	for(int j=0;j<N-1;j++){

		//bool update = false;

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

			edge e = es[i];

			if(d[e.from]!=INF && d[e.to] > d[e.from]+e.cost){

				d[e.to] = d[e.from]+e.cost;

				//update = true;

			}

		}

		//if(!update) break;

	}

	bool negative[1000];

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

		negative[i] = false;

	}

	for (int loop = 0; loop < N; ++loop) {

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

			edge e = es[i];

			if ((d[e.from] != INF && d[e.to] > d[e.from] + e.cost)) {

				d[e.to] = d[e.from] + e.cost;

				negative[e.to] = true;

			}

//			if (negative[e.from] == true) {

//					 negative[e.to] = true;

//			}

        }

    }

    return negative[N - 1];

}

//

/*

bool find_n_loop(){

	//for(int i=0;i<N;i++) d[i] = 0;



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

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

			edge e = es[j];

			if(d[e.to]>d[e.from]+e.cost){

				d[e.to] = d[e.from] + e.cost;

				if(i==N-1) return true;

			}

		}

	}

	return false;

}

*/


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

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<ll,int> pli;

#define fir first

#define sec second

#define Mp make_pair

const int MAXN = 2e5 + 5;



int a[MAXN];

ll lval[MAXN],rval[MAXN];



struct Edge

{

	int u,v;

	ll w;

};

inline bool cmp(const Edge &p,const Edge &q){ return p.w<q.w;}

vector<Edge> e;



int fa[MAXN];

inline void init(int n){ for(int i=1; i<=n; ++i) fa[i]=i;}

int find(int u){ return fa[u]==u? u: fa[u]=find(fa[u]);}

void connect(int u,int v){ fa[find(u)]=find(v);}



void gao(int l,int r)

{

	if(l==r) return;

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

	

	ll lmn = lval[l];

	int lpos = l;

	for(int i=l; i<=mid; ++i)

		if(lmn > lval[i])

			lmn = lval[i], lpos = i;

	ll rmn = rval[r];

	int rpos = r;

	for(int i=mid+1; i<=r; ++i)

		if(rmn > rval[i])

			rmn = rval[i], rpos = i;

	

	for(int i=l; i<=mid; ++i)

		e.push_back((Edge){ i, rpos, lval[i] + rmn});

	for(int i=mid+1; i<=r; ++i)

		e.push_back((Edge){ lpos, i, lmn + rval[i]});

	

	gao(l,mid); gao(mid+1,r);

}



int main(void)

{

	int n;

	ll d;

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

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

	

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

		lval[i] = a[i] - d*i,

		rval[i] = a[i] + d*i;

	

	gao(1,n);

	sort(e.begin(),e.end(),cmp);

	

	ll ans=0;

	init(n);

	for(int i=0; i<(int)e.size(); ++i)

	{

		int u=e[i].u, v=e[i].v;

		ll w=e[i].w;

		if(find(u) == find(v)) continue;

		ans += w;

		connect(u,v);

	}

	printf("%lld",ans);

	return 0;

}

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

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<ll,int> pli;

#define fir first

#define sec second

#define Mp make_pair

const int MAXN = 2e5 + 5;

const int inf = 0x3f3f3f3f;

const ll linf = 0x3f3f3f3f3f3f3f3f;



template<typename T>

void chk_min(T &a,T b){ if(a>b) a=b;}



ll a[MAXN];



int main(void)

{

	int n;	

	ll d;

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

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

	

	ll ans=0;

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

	

	for(int i=2; i<=n; ++i) chk_min(a[i], a[i-1]+d);

	for(int i=n-1; i>=1; --i) chk_min(a[i], a[i+1]+d);

	

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

	printf("%lld",ans + d*(n-1) - a[1] - a[n]);

	return 0;

}

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

using namespace std;

typedef long long ll;

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

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

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



ll BIT1[200010];

ll BIT2[200010];



void add1(int A, ll B) {

	while (A > 0) {

		BIT1[A] = min(BIT1[A], B);

		A -= A & -A;

	}

}

ll query1(int A) {

	ll kotae = 1e18;

	while (A <= 200000) {

		kotae = min(kotae, BIT1[A]);

		A += A & -A;

	}

	return kotae;

}

void add2(int A, ll B) {

	while (A <= 200000) {

		BIT2[A] = min(BIT2[A], B);

		A += A & -A;

	}

}

ll query2(int A) {

	ll kotae = 1e18;

	while (A > 0) {

		kotae = min(kotae, BIT2[A]);

		A -= A & -A;

	}

	return kotae;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	ll N, D;

	cin >> N >> D;

	int A[200001];

	rep1(i, N) cin >> A[i];



	rep1(i, 200000) BIT1[i] = 1e18;

	rep1(i, 200000) BIT2[i] = 1e18;



	rep1(i, N) {

		add1(i, A[i] + i * D);

	}

	rep1(i, N) {

		add2(i, A[i] - i * D);

	}



	ll setuyaku = 0;

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

		ll kari1 = query1(i + 1) - i * D;

		ll kari2 = query2(i - 1) + i * D;

		if (A[i] > min(kari1, kari2)) {

			setuyaku += A[i] - min(kari1, kari2);

		}

	}



	ll motomoto = 0;

	rep1(i, N - 1) motomoto += A[i];

	rep1(i, N - 1) motomoto += A[i + 1];

	motomoto += (N - 1) * D;



	co(motomoto - setuyaku);



	Would you please return 0;

}

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

using namespace std;

typedef long long ll;

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

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

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], *ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N = getint();

	ll D = getint();

	ll kotae = (N - 1) * D;

	int A[200001];

	ll C[200001];

	C[0] = 1e18;

	rep1(i, N) {

		A[i] = getint();

		kotae += A[i];

		C[i] = min(C[i - 1] + D, (ll)A[i]);

	}

	ll mae = 1e18;

	for (int i = N - 1; i > 1; i--) {

		mae = min(mae + D, (ll)A[i + 1]);

		ll kari = min(mae, C[i - 1]) + D;

		kotae += min((ll)A[i], kari);

	}

	co(kotae);



	Would you please return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// Code By H~S~C

#ifdef ONLINE_JUDGE

#pragma GCC optimize(1)

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#pragma comment(linker, "/STACK:1024000000,1024000000")

#pragma GCC optimize("Os")

#pragma GCC optimize("Og")

#pragma GCC optimize("Ofast")

#pragma GCC target("avx,sse,sse2,sse3,ssse3,sse4")

#endif

#include <initializer_list>

#include <unordered_set>

#include <unordered_map>

#include <algorithm>

#include <iostream>

#include <utility>

#include <cstdlib>

#include <cstring>

#include <vector>

#include <cstdio>

#include <queue>

#include <stack>

#include <cmath>

#include <map>

#include <set>

#define pb push_back

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

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

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

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

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

#define sqr(s) ((s)*(s))

#define MP make_pair

#define fillset(a,val) memset(a,val,sizeof(a))

#define X first

#define Y second

#define endl '\n'

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair <int,int> pii;

const int inf=0x3f3f3f3f;

const ll lnf=0x3f3f3f3f3f3f3f3f;

const double EPS=1e-9,PI=acos(-1.0);

const int mod1=1000000007,mod2=998244353;

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

const int Maxn=200005;

ll n,d,a[Maxn],dpl[Maxn],dpr[Maxn],ans;

signed main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(nullptr);cout.tie(nullptr);

	cin>>n>>d;rep(i,n) cin>>a[i],ans+=a[i];

	ans+=(n-1)*d;dpl[0]=a[0];dpr[n-1]=a[n-1];

	rep1(i,n-1) dpl[i]=min(a[i],dpl[i-1]+d);

	for (int i=n-2;~i;--i) dpr[i]=min(a[i],dpr[i+1]+d);

	rep1(i,n-2) ans+=min(dpl[i],dpr[i]);

	cout<<ans<<endl;

	return 0;

}

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

inline char gc(){

	static char buf[100000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

inline long long read(){

	long long now=0;int f=0;register char c=gc();

	for(;c<48||c>57;c=='-'&&(f=1),c=gc());for(;c>47&&c<58;now=(now<<3)+(now<<1)+c-'0',c=gc());

	return f?-now:now;

}

#define Maxn 200005

long long n,d,a[Maxn],dpl[Maxn],dpr[Maxn],ans;

long long Min(long long x, long long y) { return (((y - x) >> (64 - 1)) & (x ^ y)) ^ x; }

signed main()

{

	n=read(),d=read();

	for (int i=0;i<n;++i) a[i]=read(),ans+=a[i];

	ans+=(n-1)*d;dpl[0]=a[0];dpr[n-1]=a[n-1];

	for (int i=1;i<n;++i) dpl[i]=Min(a[i],dpl[i-1]+d);

	for (int i=n-2;~i;--i) dpr[i]=Min(a[i],dpr[i+1]+d);

	for (int i=1;i<n-1;++i) ans+=Min(dpl[i],dpr[i]);

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e 

#include <bits/stdc++.h>

using namespace std;

//#pragma GCC optimize("Ofast")

typedef long long ll;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

typedef unsigned long long ull;

#define fst first

#define sed second

#define pb push_back

#define mp make_pair

#define rt register int

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

#define rep(it, f, e) for (rt it = f; it <= e; ++it)

#define per(it, f, e) for (rt it = f; it >= e; --it)

const int MAXN = 2e5 + 10;

struct Dsu {

	int par[MAXN];

	Dsu() {

		rep (i, 1, MAXN - 1) {

			par[i] = i;

		}

	}

	inline int find(int x) {

		return x == par[x] ? x : par[x] = find(par[x]);

	}

	inline void mry(int a, int b) {

		par[find(a)] = find(b);

	}

	inline bool tog(int a, int b) {

		return find(a) == find(b);

	}

}	dsu;

ll A[MAXN], n, d;

vector<pair<ll,pii> > edge;

inline void solve(int l, int r) {

	if (l == r) return;

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

	ll ml = 1e18, li = 0;

	rep (i, l, m) {

		if (ml > A[i] - i * d) {

			ml = A[i] - i * d;

			li = i;

		}

	}

	ll mr = 1e18, ri = 0;

	rep (i, m + 1, r) {

		if (mr > A[i] + i * d) {

			mr = A[i] + i * d;

			ri = i;

		}

	}

	rep (i, l, m) {

		edge.pb(mp(A[i] - i * d + mr,mp(i, ri)));

	}

	rep (i, m + 1, r) {

		edge.pb(mp(A[i] + i * d + ml,mp(i, li)));

	}

	solve(l, m);

	solve(m + 1, r);

}

int main() {

	cin >> n >> d;

	rep (i, 1, n) {

		cin >> A[i];

	}

	solve(1, n);

	sort(all(edge));

	ll ans = 0;

	for (auto e : edge) {

	//	cerr << e.sed.fst << ' ' << e.sed.sed <<endl;

		if (!dsu.tog(e.sed.fst, e.sed.sed)) {

			ans += e.fst;

			dsu.mry(e.sed.fst, e.sed.sed);

		}

	}

	cout << ans << endl;

	return 0;

}

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

using namespace std;

//#pragma GCC optimize("Ofast")

typedef long long ll;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

typedef unsigned long long ull;

#define fst first

#define sed second

#define pb push_back

#define mp make_pair

#define rt register int

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

#define rep(it, f, e) for (rt it = f; it <= e; ++it)

#define per(it, f, e) for (rt it = f; it >= e; --it)

const int MAXN = 2e5 + 10;

int A[MAXN];

ll dpl[MAXN], dpr[MAXN];

int main() {

	ios::sync_with_stdio(false);

	cin.tie(NULL), cout.tie(NULL);

	int n, d;

	cin >> n >> d;

	ll ans = (n - 1ll) * d;

	rep (i, 1, n) {

		cin >> A[i];

		ans += A[i];

	}

	if (n == 1) {

		cout << 0 << endl;

		return 0;

	}

	dpl[1] = A[1];

	rep (i, 2, n) {

		dpl[i] = min((ll)A[i], dpl[i - 1] + d);

	}

	dpr[n] = A[n];

	per (i, n - 1, 1) {

		dpr[i] = min((ll)A[i], dpr[i + 1] + d);

	}

	rep (i, 2, n - 1) {

		ans += min(dpl[i], dpr[i]);

	}

	cout << ans <<endl;

	return 0;

}


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

#include<list>

#include<algorithm>

#include<iostream>

#include<string>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

using namespace std;

int main(){

  int i;

  int a[]={0,1,2,3,5,7,8,9},n;

  while(cin>>n&&n){

    for(i=0;pow(8,i)<=n;i++);

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

      cout<<a[n/(int)pow(8,i)];

      n%=(int)pow(8,i);

    }

    cout<<endl;

  }

  return 0;

}

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

int main(){

  int i;

  int a[11]={1},n;

  char s[9]="01235789";

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

    a[i]=a[i-1]*8;

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

    for(i=0;a[i]<=n;++i);

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

      printf("%c",s[n/a[i]]);

      n%=a[i];

    }

    puts("");

  }

  return 0;

}

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

#include <cstring>

#include <algorithm>

#include <string>

#include <cmath>

#include <stack>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <list>

#include <iostream>

#include <sstream>

#include <climits>

#include <cfloat>

#include <complex>



using namespace std;



typedef long long ll;



ll count_rooms_lesseq_than(ll newRoomNo)

{

	int t[10], d;

	for (d = 0; newRoomNo; ++d, newRoomNo /= 10)

		t[d] = newRoomNo % 10;

	for (int i = d-1; i > 0; --i)

	{

		if (t[i] == 4 || t[i] == 6)

		{

			--t[i];

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

				t[j] = 9;

			break;

		}

	}



	ll res = 0;

	for (int i = 0; i < d; ++i)

	{

		ll a = 1;

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

			a *= 8;

		res += (t[i] - (t[i] >= 6 ? 2 : t[i] >= 4 ? 1 : 0)) * a;

	}

	return res;

}

int main()

{

	int n;

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

	{

		ll l, u;

		l = 1;

		u = n * 10LL;

		while (l < u)

		{

			ll m = (l + u) / 2;

			ll t = count_rooms_lesseq_than(m);

			if (t < n)

				l = m + 1;

			else

				u = m;

		}

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

	}



	return 0;

}

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



int main()

{

	int n;

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

	{

		int t[10], d;

		for (d = 0; n; ++d, n /= 8)

			t[d] = n % 8;

		for (int i = d-1; i >= 0; --i)

			printf("%d", t[i] >= 5 ? t[i]+2 : t[i] == 4 ? t[i]+1 : t[i]);

		printf("\n");

	}



	return 0;

}

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

#include <vector>

#include <algorithm>



void ToOctalNumber(int n){

	if(!n)return;

	ToOctalNumber(n >> 3);

	std::cout << ((n&7)<4?n&7:(n&7)==4?5:(n&7)+2);

}



int main(){

	int n;

	while(std::cin >> n, n){

		ToOctalNumber(n);

		std::cout << "\n";

	}

}

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



void ToOctalNumber(int n){

	if(n){

		ToOctalNumber(n >> 3);

		printf("%d",(n&7)<4?n&7:(n&7)==4?5:(n&7)+2);

	}

}



int main(){

	int n;

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

		ToOctalNumber(n);

		puts("");

	}

}

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

using namespace std;



const int t[8] = { 0, 1, 2, 3, 5, 7, 8, 9 };



/*void solve(int n){

    if(n >= 8)

        solve(n / 8);

    cout << table[n % 8] ;

}*/



long long int solve(int n){

	long long int s=0;

	for(int i=1 ; n >0; i *= 10 , n /= 8)

		s += (long long int)t[n%8]*i;

	return s;

}

int main(){

    int n;

    

    while( cin >> n , n ){

		cout << solve(n) << endl;

    }

    

}

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

int t[]={0,1,2,3,5,7,8,9};

void s(int n){if(n>7)s(n/8);printf("%d",t[n%8]);}

main(){for(int a;scanf("%d",&a),a;puts(""))s(a);}

// Fastest known solution for this problem: