stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;



const int MAXN=100005 ;

int n , E, T , dis[MAXN] ;

long long dp[MAXN] ;



multiset<long long> st;

multiset<long long>::iterator it ;



long long calc_1(int j){

	return dp[j]-2*dis[j+1]-dis[j] ;

}



long long calc_2(int j){

	return dp[j]-dis[j] ;

}



int main(){

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

	memset(dp,0x3f,sizeof(dp)) ;

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

	dp[0]=0 ;

	int last=0 ; //第一个满足边界的

	st.insert(calc_2(0)) ;

	long long minn=(1ll<<60)-1 ;

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

		while(last<i && 2*(dis[i]-dis[last+1])>=T){

			long long tmp=calc_2(last) ;

			it=st.find(tmp) , st.erase(it) ;

			minn=min(minn,calc_1(last)) , ++last ;

		}

		dp[i]=minn+(long long)3*dis[i] ;

		if(!st.empty()) dp[i]=min(dp[i],(*st.begin())+T+dis[i]) ;

		st.insert(calc_2(i)) ;

	}

	cout << dp[n]+E-dis[n] << '\n' ;

	return 0 ;

}

// Faster C++ solution for the same problem (measured speedup: 1.8242031393530236x):
#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;



#define lowbit(a) (a&-a)

typedef long long ll;

const int maxn = 100010; const ll inf = 1LL<<60;

int N,T,E,X[maxn]; ll tree1[4*maxn],tree2[4*maxn],f[maxn];



inline int gi()

{

	char ch; int ret = 0,f = 1;

	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');

	if (ch == '-') f = -1,ch = getchar();

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

	return ret*f;

}



inline void build(int now,int l,int r)

{

	tree1[now] = tree2[now] = inf;

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

	build(now<<1,l,mid); build(now<<1|1,mid+1,r);

}



inline void modify(ll *tree,int now,int l,int r,int pos,ll key)

{

	if (l == r) { tree[now] = key; return; } int mid = (l+r)>>1;

	if (pos <= mid) modify(tree,now<<1,l,mid,pos,key);

	else modify(tree,now<<1|1,mid+1,r,pos,key);

	tree[now] = min(tree[now<<1],tree[now<<1|1]);

}



inline ll query(ll *tree,int now,int l,int r,int ql,int qr)

{

	if (ql == l&&qr == r) return tree[now]; int mid = (l+r)>>1;

	if (qr <= mid) return query(tree,now<<1,l,mid,ql,qr);

	else if (ql > mid) return query(tree,now<<1|1,mid+1,r,ql,qr);

	else return min(query(tree,now<<1,l,mid,ql,mid),query(tree,now<<1|1,mid+1,r,mid+1,qr));

}



int main()

{

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

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

	N = gi(); E = gi(); T = gi();

	for (int i = 1;i <= N;++i) X[i] = gi(),tree1[i] = tree2[i] = 1LL<<60;

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

	{

		modify(tree1,1,1,N,i,f[i-1]-2LL*(ll)X[i]-(ll)X[i-1]);

		modify(tree2,1,1,N,i,f[i-1]-(ll)X[i-1]);

		int l = 0,r = i-1,mid; f[i] = inf;

		while (l <= r)

		{

			mid = (l+r)>>1;

			if (T-2LL*(X[i]-X[mid+1]) > 0) r = mid-1;

			else l = mid+1;

		}

		if (r+1) f[i] = query(tree1,1,1,N,1,r+1)+3LL*X[i];

		if (r+2 <= i) f[i] = min(f[i],query(tree2,1,1,N,r+2,i)+(ll)X[i]+(ll)T);

	}

	cout << f[N]+(ll)E-(ll)X[N] << endl;

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;



const int MAXN=100005 ;

int n , E, T , dis[MAXN] ;

long long dp[MAXN] ;



multiset<long long> st;

multiset<long long>::iterator it ;



long long calc_1(int j){

	return dp[j]-2*dis[j+1]-dis[j] ;

}



long long calc_2(int j){

	return dp[j]-dis[j] ;

}



int main(){

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

	memset(dp,0x3f,sizeof(dp)) ;

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

	dp[0]=0 ;

	int last=0 ; //第一个满足边界的

	st.insert(calc_2(0)) ;

	long long minn=(1ll<<60)-1 ;

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

		while(last<i && 2*(dis[i]-dis[last+1])>=T){

			long long tmp=calc_2(last) ;

			it=st.find(tmp) , st.erase(it) ;

			minn=min(minn,calc_1(last)) , ++last ;

		}

		dp[i]=minn+(long long)3*dis[i] ;

		if(!st.empty()) dp[i]=min(dp[i],(*st.begin())+T+dis[i]) ;

		st.insert(calc_2(i)) ;

	}

	cout << dp[n]+E-dis[n] << '\n' ;

	return 0 ;

}

// Faster C++ solution for the same problem (measured speedup: 1.8275825652533775x):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



const int MAXN = 100005;



int n, e, T;

int x[MAXN];



void input()

{

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

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

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

}



ll f[MAXN];



void solve()

{

	f[0] = 0;

	ll minv = 1e18;

	int j = 0;

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

	{

		f[i] = f[i - 1] + T;

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

		{

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

			j++;

		}

		f[i] = min(f[i], f[j] + T);

		f[i] = min(f[i], minv + 2 * x[i]);

	}

}



void output()

{

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

}



int main()

{

	input();

	solve();

	output();



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



long long f[100010],c[100010],d[100010];

int x[100010];

int n,e,t,T;



inline void add1(int x,long long o)

{

	while(x<=n)

	{

		c[x]=min(c[x],o);

		x+=x&-x;

	}

}



inline long long ask1(int x)

{

	long long nowans=0x3f3f3f3f3f3f3f3fll;

	while(x)

	{

		nowans=min(nowans,c[x]);

		x-=x&-x;

	}

	return nowans;

}



inline void add2(int x,long long o)

{

	while(x)

	{

		d[x]=min(d[x],o);

		x-=x&-x;

	}

}



inline long long ask2(int x)

{

	long long nowans=0x3f3f3f3f3f3f3f3fll;

	while(x<=n)

	{

		nowans=min(nowans,d[x]);

		x+=x&-x;

	}

	return nowans;

}



int main()

{

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

	T=t;

	if(t%2)T++;

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

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

	memset(f,0x3f,sizeof(f));

	memset(c,0x3f,sizeof(c));

	memset(d,0x3f,sizeof(d));

	f[0]=0;

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

	{

		f[i]=min(f[i],f[i-1]+x[i]-x[i-1]+t);

		int now=upper_bound(x+1,x+1+i,x[i]-T/2)-x;

		if(x[i]-T/2>=x[1])

		{

			now--;

			long long nowans=ask1(now);

			f[i]=min(f[i],3ll*x[i]+nowans);

		}

		if(x[i]-T/2<x[1])now=0;

		now++;

		long long nowans=ask2(now);

		f[i]=min(f[i],x[i]+nowans);

		/*for(int j=i+1;j<=n;j++)

		{

			if((x[j]-x[i])*2>=t)f[j]=min(f[j],f[i-1]+3ll*(x[j]-x[i])+x[i]-x[i-1]);

			else f[j]=min(f[j],f[i-1]+t-2*(x[j]-x[i])+3ll*(x[j]-x[i])+x[i]-x[i-1]);

		}*/

		add1(i,-3ll*x[i]+f[i-1]+x[i]-x[i-1]);

		add2(i,0ll+t-x[i]+x[i]+f[i-1]-x[i-1]);

	}

	cout<<f[n]+e-x[n];

}

// Faster C++ solution for the same problem (measured speedup: 3.4444006365507156x):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



const int MAXN = 100005;



int n, e, T;

int x[MAXN];



void input()

{

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

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

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

}



ll f[MAXN];



void solve()

{

	f[0] = 0;

	ll minv = 1e18;

	int j = 0;

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

	{

		f[i] = f[i - 1] + T;

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

		{

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

			j++;

		}

		f[i] = min(f[i], f[j] + T);

		f[i] = min(f[i], minv + 2 * x[i]);

	}

}



void output()

{

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

}



int main()

{

	input();

	solve();

	output();



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define N 111111

#define M 444444

#define LL long long

using namespace std;

int n,i,k,j,a[N];LL f[N],V1[M],V2[M],E,T;

void ins(int k,int l,int r,int x,LL z1,LL z2){

	if(l==r){V1[k]=z1;V2[k]=z2;return;}

	int md=l+r>>1;

	if(x<=md)ins(k<<1,l,md,x,z1,z2);else ins(k<<1|1,md+1,r,x,z1,z2);

	V1[k]=min(V1[k<<1],V1[k<<1|1]);

	V2[k]=min(V2[k<<1],V2[k<<1|1]);

}

LL qu1(int k,int l,int r,int x,int y){

	if(x>y)return 1e18;

	if(x<=l&&r<=y)return V1[k];

	int md=l+r>>1;

	if(y<=md)return qu1(k<<1,l,md,x,y);

	if(x>md)return qu1(k<<1|1,md+1,r,x,y);

	return min(qu1(k<<1,l,md,x,y),qu1(k<<1|1,md+1,r,x,y));

}

LL qu2(int k,int l,int r,int x,int y){

	if(x>y)return 1e18;

	if(x<=l&&r<=y)return V2[k];

	int md=l+r>>1;

	if(y<=md)return qu2(k<<1,l,md,x,y);

	if(x>md)return qu2(k<<1|1,md+1,r,x,y);

	return min(qu2(k<<1,l,md,x,y),qu2(k<<1|1,md+1,r,x,y));

}

int main(){

	for(i=0;i<M;i++)V1[i]=V2[i]=1e18;

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

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

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

		f[i]=1e18;

		for(;(a[i]-a[k+1])*2>T&&k<i;k++);

		//f[i]=f[k]+max(a[i]-a[k+1]+a[i]-a[k+1],T)+a[i]-a[k];

		//j<=k a[i]-a[j+1*2>T

		//f[i]=qu2(1,0,0,k)

	//	printf("%d %d\n",(a[i]-a[k+1])*2,T);

		if(i==0)f[i]=0;else 

		f[i]=min(qu1(1,0,n,k,i-1)+T+a[i],qu2(1,0,n,0,k-1)+1ll*a[i]*3);

		//printf("%lld %lld\n",qu1(1,0,n,k,i-1)+T+a[i],qu2(1,0,n,0,k-1)+1ll*a[i]*3);

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

	//	printf("%lld %lld %d\n",qu1(1,0,n,k,i-1),qu2(1,0,n,0,k-1),T+a[i]);

		//puts("-----------------------");

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

		

		ins(1,0,n,i,f[i]-a[i],f[i]-a[i]-a[i+1]*2);

	}

	printf("%lld\n",f[n]+E-a[n]);

}

// Faster C++ solution for the same problem (measured speedup: 8.626100380268966x):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



const int MAXN = 100005;



int n, e, T;

int x[MAXN];



void input()

{

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

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

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

}



ll f[MAXN];



void solve()

{

	f[0] = 0;

	ll minv = 1e18;

	int j = 0;

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

	{

		f[i] = f[i - 1] + T;

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

		{

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

			j++;

		}

		f[i] = min(f[i], f[j] + T);

		f[i] = min(f[i], minv + 2 * x[i]);

	}

}



void output()

{

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

}



int main()

{

	input();

	solve();

	output();



	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int d[N], T;

long long dp[N];

long long calc_big(int j) {

	return T - d[j] + dp[j];

}

long long calc_small(int j) {

	return 2LL * (-d[j + 1]) - d[j] + dp[j];

}

struct cmp_big {

	bool operator () (const int &i, const int &j) {

		return calc_big(i) > calc_big(j);

	}

};

struct cmp_small {

	bool operator () (const int &i, const int &j) {

		return calc_small(i) > calc_small(j);

	}

};

int main() {

	int n, E;

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

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

	priority_queue<int, vector<int>, cmp_big> q1;

	priority_queue<int, vector<int>, cmp_small> q2;

	q1.push(0);

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

		while (!q1.empty() && 2LL * (d[i] - d[q1.top() + 1]) >= T) {

			q2.push(q1.top());

			q1.pop();

		}

		dp[i] = 1e18;

		if (!q1.empty()) {

			int j = q1.top();

			dp[i] = min(dp[i], d[i] + calc_big(j));

		}

		if (!q2.empty()) {

			int j = q2.top();

			dp[i] = min(dp[i], 3LL * d[i] + calc_small(j));

		}

		q1.push(i);

	}

	cout << dp[n] + E - d[n] << endl;

}




// Faster C++ solution for the same problem (measured speedup: 5.228267294504995x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

const int maxn=100010;

int n,e;

ll T;

int x[maxn];

ll f[maxn];



int main()

{

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

	cin>>T;

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

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

	f[0]=0;

	f[1]=T;

	int la=0;

	ll minx=1LL<<60;

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

	{

		while (2LL*(x[i]-x[la+1])>T)

		{

			ll tmp=f[la]-2LL*x[la+1];

			if (minx>tmp)	minx=tmp;

			la++;

		}

		f[i]=f[i-1]+T;

		if (la>0)

			f[i]=min(f[i],minx+2LL*x[i]);

		f[i]=min(f[i],f[la]+T);

	}

	cout<<f[n]+e<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.243179426708469x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<set>

#define LL long long

using namespace std;

multiset<LL> s1, s2;

LL dp[110000], dp2[110000];

int x[110000], n, E, T;

int main(){

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

	dp2[0] = T;s1.insert(T);

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

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

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

			s1.erase(s1.find(dp2[j]));

			dp2[j] = dp2[j] - T - 2 * (x[j + 1]);

			s2.insert(dp2[j]);

			j++;

		}

		dp2[i] = (((LL)1)<<50);

		if(!s1.empty()) dp[i] = max(dp[i], *s1.begin() + x[i]);

		if(!s2.empty()) dp[i] = min(dp[i], *s2.begin() + (LL)3 * x[i]);

		dp2[i] = dp[i] - x[i] + T; 

		s1.insert(dp2[i]);

	}

	cout<<dp[n] - x[n] + E;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.221497201328246x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;



const int MAXN=100005 ;

int n , E, T , dis[MAXN] ;

long long dp[MAXN] ;



multiset<long long> st;

multiset<long long>::iterator it ;



long long calc_1(int j){

	return dp[j]-2*dis[j+1]-dis[j] ;

}



long long calc_2(int j){

	return dp[j]-dis[j] ;

}



int main(){

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

	memset(dp,0x3f,sizeof(dp)) ;

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

	dp[0]=0 ;

	int last=0 ; //第一个满足边界的

	st.insert(calc_2(0)) ;

	long long minn=(1ll<<60)-1 ;

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

		while(last<i && 2*(dis[i]-dis[last+1])>=T){

			long long tmp=calc_2(last) ;

			it=st.find(tmp) , st.erase(it) ;

			minn=min(minn,calc_1(last)) , ++last ;

		}

		dp[i]=minn+(long long)3*dis[i] ;

		if(!st.empty()) dp[i]=min(dp[i],(*st.begin())+T+dis[i]) ;

		st.insert(calc_2(i)) ;

	}

	cout << dp[n]+E-dis[n] << '\n' ;

	return 0 ;

}

// Faster C++ solution for the same problem (measured speedup: 9.420530221449255x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



long long f[100010],c[100010],d[100010];

int x[100010];

int n,e,t,T;



inline void add1(int x,long long o)

{

	while(x<=n)

	{

		c[x]=min(c[x],o);

		x+=x&-x;

	}

}



inline long long ask1(int x)

{

	long long nowans=0x3f3f3f3f3f3f3f3fll;

	while(x)

	{

		nowans=min(nowans,c[x]);

		x-=x&-x;

	}

	return nowans;

}



inline void add2(int x,long long o)

{

	while(x)

	{

		d[x]=min(d[x],o);

		x-=x&-x;

	}

}



inline long long ask2(int x)

{

	long long nowans=0x3f3f3f3f3f3f3f3fll;

	while(x<=n)

	{

		nowans=min(nowans,d[x]);

		x+=x&-x;

	}

	return nowans;

}



int main()

{

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

	T=t;

	if(t%2)T++;

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

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

	memset(f,0x3f,sizeof(f));

	memset(c,0x3f,sizeof(c));

	memset(d,0x3f,sizeof(d));

	f[0]=0;

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

	{

		f[i]=min(f[i],f[i-1]+x[i]-x[i-1]+t);

		int now=upper_bound(x+1,x+1+i,x[i]-T/2)-x;

		if(x[i]-T/2>=x[1])

		{

			now--;

			long long nowans=ask1(now);

			f[i]=min(f[i],3ll*x[i]+nowans);

		}

		if(x[i]-T/2<x[1])now=0;

		now++;

		long long nowans=ask2(now);

		f[i]=min(f[i],x[i]+nowans);

		/*for(int j=i+1;j<=n;j++)

		{

			if((x[j]-x[i])*2>=t)f[j]=min(f[j],f[i-1]+3ll*(x[j]-x[i])+x[i]-x[i-1]);

			else f[j]=min(f[j],f[i-1]+t-2*(x[j]-x[i])+3ll*(x[j]-x[i])+x[i]-x[i-1]);

		}*/

		add1(i,-3ll*x[i]+f[i-1]+x[i]-x[i-1]);

		add2(i,0ll+t-x[i]+x[i]+f[i-1]-x[i-1]);

	}

	cout<<f[n]+e-x[n];

}

// Faster C++ solution for the same problem (measured speedup: 17.75464534862557x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

const long long inf=1LL<<61;

typedef long long LL;

struct sgt{

	LL mn[maxn*2];

	int id(int l,int r){return l+r|l!=r;}



	void build(int l,int r){

		mn[id(l,r)]=inf;

		if(l==r)return ;

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

		build(l,mid);

		build(mid+1,r);

	}

	LL Q(int l,int r,int l0,int r0){

		if(l0<=l&&r0>=r)

			return mn[id(l,r)];

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

		LL ans=inf;

		if(l0<=mid)ans=min(ans,Q(l,mid,l0,r0));

		if(r0>mid)ans=min(ans,Q(mid+1,r,l0,r0));

		return ans;

	}

	void C(int l,int r,int ps,LL val){

		if(l==r){

			mn[id(l,r)]=val;

			return ;

		}

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

		if(ps<=mid)C(l,mid,ps,val);

		else C(mid+1,r,ps,val);

		mn[id(l,r)]=min(mn[id(l,mid)],mn[id(mid+1,r)]);

	}

}T1,T2;

int n;

LL T,E;

LL d[maxn];

LL dp[maxn],d2[maxn];



LL bf(){



	dp[1]=0;

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

		dp[i]=inf;

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

			dp[i]=min(dp[i],dp[j-1]+d[i]-d[j-1]+max(T,2*(d[i]-d[j])));

		}

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

	}





	LL ans=dp[n]+E-d[n];



	return ans;

}



int main(){

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

	n++;

	d[1]=0;

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

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

		d2[i]=d[i]*2;

	}





	//TODO

//	cout<< bf() <<endl;

//	return 0;

	T1.build(1,n);

	T2.build(1,n);





	dp[1]=0;

	T1.C(1,n,1,0);

	T2.C(1,n,1,0);



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



		dp[i]=dp[i-1]+d[i]-d[i-1]+T;





		auto bin=[&](int lef,int rig){

			int l=1,r=rig-1;



			while(l<r){

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

				if(2*(d[rig]-d[mid])>=T)

					l=mid+1;

				else

					r=mid;

			}



			int ans=0;

			for(int delta=-10;delta<=10;delta++){

				int ps=delta+l;

				if(1<=ps&&ps<rig){

					if(2*(d[rig]-d[ps])>=T){

						ans=ps;

					}else{

						break;

					}

				}

			}



			return ans;

		};

		int ps=bin(1,i);

		/*

		int ps=0;

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

			if(2*(d[i]-d[j])>=T){

				ps=j;

			}else{

				break;

			}

		}

*/

//		cerr<<ps<<" "<<bin(1,i)<<endl; 

//		assert(bin(1,i)==ps);



		//assert(ps==bin(1,i));



//		cerr<<"it is "<<i<<" "<<ps<<endl;

		LL res1=inf,res2=inf;



		if(ps>=1)

			res1=T1.Q(1,n,1,ps)+3*d[i];



		if(ps+1<=i-1)

			res2=T2.Q(1,n,ps+1,i-1)+d[i]+T;

//		cerr<<res1<<" "<<res2<<endl;



		dp[i]=min(dp[i],res1);

		dp[i]=min(dp[i],res2);

//		cerr<<"dp = "<<dp[i]<<endl;

		T1.C(1,n,i,dp[i-1]-d[i-1]-2*d[i]);

		T2.C(1,n,i,dp[i-1]-d[i-1]);

	}



	LL ans=dp[n]+E-d[n];



	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2262390629854x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

const long long inf=1LL<<61;

typedef long long LL;

struct sgt{

	LL mn[maxn*2];

	int id(int l,int r){return l+r|l!=r;}



	void build(int l,int r){

		mn[id(l,r)]=inf;

		if(l==r)return ;

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

		build(l,mid);

		build(mid+1,r);

	}

	LL Q(int l,int r,int l0,int r0){

		if(l0<=l&&r0>=r)

			return mn[id(l,r)];

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

		LL ans=inf;

		if(l0<=mid)ans=min(ans,Q(l,mid,l0,r0));

		if(r0>mid)ans=min(ans,Q(mid+1,r,l0,r0));

		return ans;

	}

	void C(int l,int r,int ps,LL val){

		if(l==r){

			mn[id(l,r)]=val;

			return ;

		}

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

		if(ps<=mid)C(l,mid,ps,val);

		else C(mid+1,r,ps,val);

		mn[id(l,r)]=min(mn[id(l,mid)],mn[id(mid+1,r)]);

	}

}T1,T2;

int n;

LL T,E;

LL d[maxn];

LL dp[maxn],d2[maxn];



LL bf(){



	dp[1]=0;

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

		dp[i]=inf;

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

			dp[i]=min(dp[i],dp[j-1]+d[i]-d[j-1]+max(T,2*(d[i]-d[j])));

		}

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

	}





	LL ans=dp[n]+E-d[n];



	return ans;

}



int main(){

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

	n++;

	d[1]=0;

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

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

		d2[i]=d[i]*2;

	}





	//TODO

//	cout<< bf() <<endl;

//	return 0;

	T1.build(1,n);

	T2.build(1,n);





	dp[1]=0;

	T1.C(1,n,1,0);

	T2.C(1,n,1,0);



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



		dp[i]=dp[i-1]+d[i]-d[i-1]+T;





		auto bin=[&](int lef,int rig){

			int l=1,r=rig-1;



			while(l<r){

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

				if(2*(d[rig]-d[mid])>=T)

					l=mid+1;

				else

					r=mid;

			}



			int ans=0;

			for(int delta=-5;delta<=5;delta++){

				int ps=delta+l;

				if(1<=ps&&ps<rig){

					if(2*(d[rig]-d[ps])>=T){

						ans=ps;

					}else{

						break;

					}

				}

			}



			return ans;

		};

		int ps=bin(1,i);

		/*

		int ps=0;

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

			if(2*(d[i]-d[j])>=T){

				ps=j;

			}else{

				break;

			}

		}

*/

//		cerr<<ps<<" "<<bin(1,i)<<endl; 

//		assert(bin(1,i)==ps);



		//assert(ps==bin(1,i));



//		cerr<<"it is "<<i<<" "<<ps<<endl;

		LL res1=inf,res2=inf;



		if(ps>=1)

			res1=T1.Q(1,n,1,ps)+3*d[i];



		if(ps+1<=i-1)

			res2=T2.Q(1,n,ps+1,i-1)+d[i]+T;

//		cerr<<res1<<" "<<res2<<endl;



		dp[i]=min(dp[i],res1);

		dp[i]=min(dp[i],res2);

//		cerr<<"dp = "<<dp[i]<<endl;

		T1.C(1,n,i,dp[i-1]-d[i-1]-2*d[i]);

		T2.C(1,n,i,dp[i-1]-d[i-1]);

	}



	LL ans=dp[n]+E-d[n];



	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.18696155771385x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}