stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



struct Node{

	int p, q;

};



const int N = 1e5 + 10;



Node a[N];

long long sum[N];

priority_queue <int, vector <int>, greater <int> > pq;



bool cmp(const Node& x, const Node& y){

	return x.p - x.q < y.p - y.q;

}



int main(){

	int x, y, z, n, n1, n2, n3;

	long long ans, rec, maxx;

	scanf("%d %d %d",&x,&y,&z);

	n = x + y + z;

	ans = 0;

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

		scanf("%d %d %d",&n1,&n2,&n3);

		a[i].p = n1 - n3; a[i].q = n2 - n3;

		ans += n3;

	}

	sort(a + 1, a + n + 1, cmp);

	memset(sum, 0, sizeof(sum));

	rec = 0;

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

		pq.push(a[i].q);

		rec += a[i].q;

	}

	sum[y] = rec;

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

		if (a[i].q > pq.top()){

			rec += a[i].q - pq.top();

			pq.pop();

			pq.push(a[i].q);

		}

		sum[i] = rec;

	}

	while (!pq.empty()) pq.pop();

	rec = 0;

	for (int i = n; i >= n - x + 1; i--){

		pq.push(a[i].p);

		rec += a[i].p;

	}

	sum[n - x] += rec;

	for (int i = n - x; i > y; i--){

		if (a[i].p > pq.top()){

			rec += a[i].p - pq.top();

			pq.pop();

			pq.push(a[i].p);

		}

		sum[i - 1] += rec;

	}

	maxx = -1e18;

	for (int i = y; i <= n - x; i++) maxx = max(maxx, sum[i]);

	ans += maxx;

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

	return 0;

}

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

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <queue>

#include <algorithm>

#define N 201000

#define int long long

typedef long long ll;

template<typename T> inline void read(T &x) {

  x = 0; char c = getchar();

  while (!isdigit(c)) c = getchar();

  while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }

}

using namespace std;

const int inf = 1e18;

inline void MAX(ll &a, ll b) {

  if (b > a)  a = b;

}

int A, B, C, n;

ll ans = -inf, tmp;

struct node {

  int a, b;

}nd[N];

bool cmp(const node &a, const node &b) {

  return a.a - a.b > b.a - b.b;

}

ll f[N];

priority_queue<int, vector<int>, greater<int> > q;

inline void work() {

  ll res = 0;

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

    q.push(nd[i].a); res += nd[i].a;

  }

  f[A] = res;

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

    int a = nd[i].a;

    if (q.top() < a)  res -= q.top(), q.pop(), q.push(a), res += a;

    f[i] = res;

  }

  while (!q.empty())  q.pop();

  res = 0;

  for (int i = n; i > n - B; --i) q.push(nd[i].b), res += nd[i].b;

  MAX(ans, res + f[n - B]);

  for (int i = n - B; i > A; --i) {

    int b = nd[i].b;

    if (q.top() < b)  res -= q.top(), q.pop(), q.push(b), res += b;

    MAX(ans, res + f[i - 1]);

  }

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

}

signed main() {

  read(A), read(B), read(C);

  n = A + B + C;

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

    int a, b, c; read(a), read(b), read(c);

    tmp += c;

    nd[i] = (node){a - c, b - c};

  }

  sort(nd + 1, nd + 1 + n, cmp);

  work();

  return 0;

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

using namespace std;



int main (){

	long long a, b, v, w, t;

	scanf("%lld%lld%lld%lld%lld", &a, &v, &b, &w, &t);

	if(v * t >= ((a - b) > 0 ? (a - b) : (b - a)) + w * t){

		puts("YES");

		return 0;

	}

	puts("NO");

	return 0;

}


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



typedef long long ll;



ll myabs(ll a) {

	return a > 0 ? a : -a;

}



int main() {

	ll a, b, v, w, t;

	scanf("%lld%lld%lld%lld%lld", &a, &v, &b, &w, &t);

	ll dif = myabs(a - b);

	if (dif > t * (v - w))

		puts("NO");

	else

		puts("YES");

	return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

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<int> 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 = 1000 * 1000 + 47;



int n, e, t;

int X[MAX];

LL dp[MAX];



int main()

{

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

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

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

	int n, e, t;

	cin >> n >> e >> t;

	FOR(i, 0, n)

	{

		cin >> X[i];

	}



	FOR(i, 0, n + 1) dp[i] = INF;

	dp[0] = 0;

	int p = 0;

	LL minn = LINF;



	FOR(i, 1, n + 1)

	{

		while (2 * (X[i - 1] - X[p]) > t)

		{

			minn = min(dp[p] - 2 * X[p], minn);

			p++;

		}



		dp[i] = minn + 2 * X[i - 1];

		dp[i] = min(dp[i], dp[p] + t);

	}



	cout << dp[n] + e;

}


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

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

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

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

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

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

	{

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

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

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

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

#include<cstdio>

#include<set>

using namespace std;

long long dp[100010];

int x[100010];

int n,e;

long long t;

int st;

multiset<long long>s1,s2;

int main()

{

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

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

	s2.insert(t);

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

	{

		while(st+1<i && 2*(x[i]-x[st+1])>=t)

		{

			s2.erase(s2.find(dp[st]-x[st]+t));

			s1.insert(dp[st]-x[st]-2LL*x[st+1]);

			st++;

		}

		dp[i]=4e18;

		if(s1.size())dp[i]=min(dp[i],(*s1.begin())+3LL*x[i]);

		if(s2.size())dp[i]=min(dp[i],x[i]+(*s2.begin())),

		s2.insert(dp[i]-x[i]+t);

	}

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

	return 0;

} 

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

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

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

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

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

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

	{

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

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

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

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

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



ll x[111111];

ll dp[111111];

int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	ll lmin=ll(1e18); 

	deque<pair<ll,ll> > rmin;

	int n; cin>>n; ll e,t; cin>>e>>t;

	x[0]=0;

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

	{

		cin>>x[i];

	}

	int ptr=1;

	rmin.pb(mp(dp[0]-x[0]+t,1));

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

	{

		while(ptr<=i&&x[i]>=t/2+x[ptr]+1) //this means that we need to remove ptr from the "T - 2(x_i - x_{j+1})" is large part

		{

			if(!rmin.empty()&&rmin.front().se==ptr) rmin.pop_front();

			lmin = min(lmin, dp[ptr-1]-2*x[ptr]-x[ptr-1]);

			ptr++;

		}

		ll best=lmin;

		if(!rmin.empty()) best=min(best,-2*x[i]+rmin.front().fi);

		dp[i]=best+3LL*x[i];

		ll cost = dp[i]-x[i]+t;

		while(!rmin.empty()&&rmin.back().fi>=cost) rmin.pop_back();

		rmin.pb(mp(cost,i+1));

	}

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

}


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

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

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

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

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

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

	{

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

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

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

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#include<queue>

#include<set>

#include<map>

#define ll long long

#define inf 1e9

#define eps 1e-10

#define mod 9901

#define mkp make_pair

using namespace std;

int i,j,k,m,s,t,n,ans1,ans2,n1,nn,m1,mx;

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;

}

int kabs(int a)

{

   if (a<0) return -a;

   return a; 

}

void add(int &x,int y)

{

   x+=y;

   if (x>=mod) x-=mod;

}

void dec(int &x,int y)

{

	x-=y;

	if (x<0) x+=mod;

}

int a[101000];

ll f[101000];

int main()

{

	int e;

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

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

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

	j=0;

	ll s=1e18;

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

		f[i]=1e18;

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

	{

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

			s=min(s,f[j]-2ll*a[j+1]),j++;

		f[i]=min(f[j]+t,2ll*a[i]+s);

	}

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

}

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

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

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

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

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

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

	{

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

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

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

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

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<int> 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 = 1000 * 1000 + 47;



int n, e, t;

int X[MAX];

LL dp[MAX];



int main()

{

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

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

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

	int n, e, t;

	cin >> n >> e >> t;

	FOR(i, 0, n)

	{

		cin >> X[i];

	}



	FOR(i, 0, n + 1) dp[i] = INF;

	dp[0] = 0;

	int p = 0;

	LL minn = LINF;



	FOR(i, 1, n + 1)

	{

		while (2 * (X[i - 1] - X[p]) > t)

		{

			minn = min(dp[p] - 2 * X[p], minn);

			p++;

		}



		dp[i] = minn + 2 * X[i - 1];

		dp[i] = min(dp[i], dp[p] + t);

	}



	cout << dp[n] + e;

}


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

#include<algorithm>

using namespace std;



typedef long long ll;

const int MAXN=100005;

const ll INF=1e18;



int n,m,T;

int a[MAXN];

ll d[MAXN],mine=INF;



int main(){



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

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

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

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

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

            last++;

        }

        d[i]=d[last]+T;

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

    }

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



    fclose(stdin);

    fclose(stdout);

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

#include<cstdio>

#include<set>

using namespace std;

long long dp[100010];

int x[100010];

int n,e;

long long t;

int st;

multiset<long long>s1,s2;

int main()

{

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

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

	s2.insert(t);

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

	{

		while(st+1<i && 2*(x[i]-x[st+1])>=t)

		{

			s2.erase(s2.find(dp[st]-x[st]+t));

			s1.insert(dp[st]-x[st]-2LL*x[st+1]);

			st++;

		}

		dp[i]=4e18;

		if(s1.size())dp[i]=min(dp[i],(*s1.begin())+3LL*x[i]);

		if(s2.size())dp[i]=min(dp[i],x[i]+(*s2.begin())),

		s2.insert(dp[i]-x[i]+t);

	}

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

	return 0;

} 

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

#include<algorithm>

using namespace std;



typedef long long ll;

const int MAXN=100005;

const ll INF=1e18;



int n,m,T;

int a[MAXN];

ll d[MAXN],mine=INF;



int main(){



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

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

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

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

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

            last++;

        }

        d[i]=d[last]+T;

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

    }

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



    fclose(stdin);

    fclose(stdout);

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

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



ll x[111111];

ll dp[111111];

int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	ll lmin=ll(1e18); 

	deque<pair<ll,ll> > rmin;

	int n; cin>>n; ll e,t; cin>>e>>t;

	x[0]=0;

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

	{

		cin>>x[i];

	}

	int ptr=1;

	rmin.pb(mp(dp[0]-x[0]+t,1));

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

	{

		while(ptr<=i&&x[i]>=t/2+x[ptr]+1) //this means that we need to remove ptr from the "T - 2(x_i - x_{j+1})" is large part

		{

			if(!rmin.empty()&&rmin.front().se==ptr) rmin.pop_front();

			lmin = min(lmin, dp[ptr-1]-2*x[ptr]-x[ptr-1]);

			ptr++;

		}

		ll best=lmin;

		if(!rmin.empty()) best=min(best,-2*x[i]+rmin.front().fi);

		dp[i]=best+3LL*x[i];

		ll cost = dp[i]-x[i]+t;

		while(!rmin.empty()&&rmin.back().fi>=cost) rmin.pop_back();

		rmin.pb(mp(cost,i+1));

	}

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

}


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

#include<algorithm>

using namespace std;



typedef long long ll;

const int MAXN=100005;

const ll INF=1e18;



int n,m,T;

int a[MAXN];

ll d[MAXN],mine=INF;



int main(){



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

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

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

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

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

            last++;

        }

        d[i]=d[last]+T;

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

    }

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



    fclose(stdin);

    fclose(stdout);

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#include<queue>

#include<set>

#include<map>

#define ll long long

#define inf 1e9

#define eps 1e-10

#define mod 9901

#define mkp make_pair

using namespace std;

int i,j,k,m,s,t,n,ans1,ans2,n1,nn,m1,mx;

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;

}

int kabs(int a)

{

   if (a<0) return -a;

   return a; 

}

void add(int &x,int y)

{

   x+=y;

   if (x>=mod) x-=mod;

}

void dec(int &x,int y)

{

	x-=y;

	if (x<0) x+=mod;

}

int a[101000];

ll f[101000];

int main()

{

	int e;

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

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

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

	j=0;

	ll s=1e18;

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

		f[i]=1e18;

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

	{

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

			s=min(s,f[j]-2ll*a[j+1]),j++;

		f[i]=min(f[j]+t,2ll*a[i]+s);

	}

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

}

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

#include<algorithm>

using namespace std;



typedef long long ll;

const int MAXN=100005;

const ll INF=1e18;



int n,m,T;

int a[MAXN];

ll d[MAXN],mine=INF;



int main(){



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

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

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

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

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

            last++;

        }

        d[i]=d[last]+T;

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

    }

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



    fclose(stdin);

    fclose(stdout);

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

typedef long long ll;

using namespace std;

const int MAXN=1e5+5;

const ll inf=(1ll<<63-1);

ll a[MAXN];

ll dp[MAXN];

int main()

{

 

    ll n,e,t;

    cin>>n>>e>>t;

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

    {

        cin>>a[i];

    }

    memset(dp,(ll)0x3f3f3f3f,sizeof(dp));

    dp[0]=0;

    ll mn=inf;

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

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

        {

            mn=min(mn,dp[now]-2*a[now+1]);

            now++;

        }

        dp[i]=dp[now]+t;

        dp[i]=min(dp[i],mn+2*a[i]);

 

    }

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

    return 0;

 

}

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

#define ll long long

using namespace std;

ll n,S,T,i,la,now,f[200001],a[200001];

int main(){

	scanf("%lld%lld%lld",&n,&S,&T);

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

	la=0;now=1e9;

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

		while(la<i&&2*(a[i]-a[la+1])>T){

			now=min(now,f[la]-2*a[la+1]);

			la++;

		}

		f[i]=min(2*a[i]+now,f[la]+T);

	}

	f[n]+=a[n]+abs(a[n]-S);

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

}

/*

最后肯定被分成一段段 

*/
// 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.8253851210836762x):
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;



const int N = 1e5 + 10;

const long long inf = 1e17 + 7;



int n, E, T, d[N];



struct node {

	int l, r;

	long long max;	

};

	

struct segTree {

	node h[N << 2];

	int p[N];

	

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

		h[x].l = l; h[x].r = r; h[x].max = -inf;

		if (l == r) {

			p[l] = x;

			return;

		}

		int m = (l + r) / 2, L = x * 2, R = L + 1;

		build(L, l, m); build(R, m + 1, r);

	}

	void init(int n) {

		build(1, 1, n);

	}

	

	void modify(int x, int l, int r, long long k) {

		if (l > r) return;

		if (h[x].l == l && h[x].r == r) {

			h[x].max = max(h[x].max, k);

			return;	

		}

		

		int m = (h[x].l + h[x].r) / 2;

		int L = x * 2, R = L + 1;

		h[L].max = max(h[L].max, h[x].max);

		h[R].max = max(h[R].max, h[x].max);

		

		if (r <= m) modify(L, l, r, k);

		else if (l >= m + 1) modify(R, l, r, k);

		else {

			modify(L, l, m, k);

			modify(R, m + 1, r, k);	

		}

	}

	

	long long getmax(int id) {

		int x = p[id];

		long long res = -inf;

		while (x) {

			res = max(res, h[x].max);

			x /= 2;

		}

		return res;

	}

} a, b;



int Find(int l, int r, long long k) {

	while (l < r) {

		int m = (l + r) / 2;

		if (m == n + 1 || 2 * d[m] >= k) r = m;

		else l = m + 1;

	}

	return l;

}



int main() {

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

	d[0] = 0;

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

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

	a.init(n); b.init(n);

	long long ans = 0;

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

		int t;

		t = Find(i, n + 1, 1LL * T + 2 * d[i]);

		//printf("...%d %d\n", i, t);

		a.modify(1, i, t - 1, ans - 2 * d[i - 1] - T);

		b.modify(1, t, n, ans + 2 * d[i] - 2 * d[i - 1]);

		ans = max(a.getmax(i) + 2 * d[i], b.getmax(i));

		//printf("%d %lld\n", i, ans);

	}

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

	printf("%lld\n", -ans + 2 * d[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: 1.799606090446841x):
#include<iostream>

#include<queue>

using namespace std;

long long f[101010];

long long x[101010];

long long E,T;

long long calc(int i,int j)

{

	return max(f[j-1]+T,f[j-1]+2*x[i]-2*x[j]);

}

priority_queue<long long> Q;

int main()

{

	int n;

	cin>>n>>E>>T;

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

		cin>>x[i];

	f[1]=T;

	int now=0;

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

	{

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

		int l=1,r=i-1;

		while(r>l)

		{

			int m=(l+r)/2;

			if(T-2*x[i]+2*x[m]>=0)

				r=m;

			else

				l=m+1;

		}

		f[i]=min(f[i],max(f[l-1]+T,f[l-1]+2*x[i]-2*x[l]));

		if(l>1)

		{

			while(now<l-1)

			{

				now++;

				Q.push(2*x[now]-f[now-1]);

			}

			f[i]=min(f[i],2*x[i]-Q.top());

		}

	}

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

	return 0;

}