## Editorial for Mua vé tàu hoả

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const maxn=100011;
var a,b:array[1..maxn] of int64;
s,f,n:longint;
l,c:array[1..3] of int64;

procedure rf;
var i:longint;
begin
for i:=1 to 3 do read(l[i]);
for i:=1 to 3 do read(c[i]);
for i:=2 to n do readln(a[i]);
end;

procedure pr;
var i,j,k,t:longint;
begin
for i:=1 to n do b[i]:=maxlongint*10000;
b[s]:=0;
for j:=s+1 to f do
for i:=j-1 downto s do
begin
if a[j]>a[i]+l[3] then break;
for k:=1 to 3 do
if (a[j]-a[i]<=l[k]) and (b[j]>b[i]+c[k]) then
begin
b[j]:=b[i]+c[k];
break;
end;
end;
end;

procedure wf;
begin
write(b[f]);
end;

begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 100005

typedef long long LL;
int l[3], c[3], n, s, f; //a[i] = k/c giua ga 1 va ga i
long long d[N], a[N];

void enter() {
scanf("%d%d%d%d%d%d%d%d%d",l,l+1,l+2,c,c+1,c+2,&n,&s,&f);
if(s>f) swap(s,f);
fo(i,2,n) scanf("%lld",a+i);
}

//LL min(LL a, LL b) { return a < b ? a : b; }

void process() {
fill(d+s+1, d+n+1, LLONG_MAX-2*INF);
fo(i,s+1,f) {
rep(k,3) {
int p = lower_bound(a+1, a+n+1, a[i] - l[k]) - a;
d[i] = min(d[i], d[p] + c[k]);
}
}
cout << d[f] << endl;
//cout << *min_element(d+f, d+n+1) << endl;
}

int main() {
//freopen("input.txt", "r", stdin);
enter();
process();
return 0;
}


#### Code mẫu của ladpro98

program qbticket;
uses    math;
const   fi='';
maxN=100005;
oo=trunc(1e18);
var     a,f:array[1..maxN] of int64;
n,st,fin,l1,l2,l3,c1,c2,c3:longint;

procedure input;
var     inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
a[1]:=0;
for i:=2 to n do
close(inp);

end;

function find(r:longint;key:int64):longint;
var     l,m,k:longint;
begin
l:=st;
while l<=r do
begin
m:=(l+r) shr 1;
if a[m]>=key then
begin
k:=m;
r:=m-1;
end
else l:=m+1;
end;
exit(k);
end;

procedure dp;
var     i,x,y,z:longint;
begin
f[st]:=0;
for i:=st+1 to fin do
begin
x:=find(i,a[i]-l1);
y:=find(i,a[i]-l2);
z:=find(i,a[i]-l3);
f[i]:=oo;
if x<>i then f[i]:=min(f[i],f[x]+c1);
if y<>i then f[i]:=min(f[i],f[y]+c2);
if z<>i then f[i]:=min(f[i],f[z]+c3);
end;
end;

begin
input;
dp;
write(f[fin]);
end.


#### Code mẫu của RR

{\$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=100111;
oo=1000000000000000001;
var
f1,f2:text;
n,l1,l2,l3,c1,c2,c3,s,t,start,target:int64;
vt,ind:array[1..MAXN] of int64;
d:array[1..MAXN] of int64;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
for i:=2 to n do read(f1,vt[i]);
for i:=1 to n do ind[i]:=i;
end;
procedure swap(var a,b:int64);
var
temp:int64;
begin
temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:int64);
var
i,j,mid:int64;
begin
i:=l; j:=r; mid:=vt[l+random(r-l+1)];
repeat
while vt[i]<mid do inc(i);
while vt[j]>mid do dec(j);
if i<=j then
begin
swap(vt[i],vt[j]);
swap(ind[i],ind[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure solve;
var
i1,i2,i3:int64;
i:longint;
begin
//  for i:=2 to n do if ind[i]=s then start:=i;
//  for i:=2 to n do if ind[i]=t then target:=i;
start:=s; target:=t;
if start>target then swap(start,target);
d[start]:=0; i1:=start; i2:=start; i3:=start;
for i:=1+start to target do
begin
d[i]:=oo;
//Cap nhat theo loai 1
while (vt[i]-vt[i1]>l1) do inc(i1);
d[i]:=min(d[i],d[i1]+c1);
//Cap nhat theo loai 2
while (vt[i]-vt[i2]>l2) do inc(i2);
d[i]:=min(d[i],d[i2]+c2);
//Cap nhat theo loai 3
while (vt[i]-vt[i3]>l3) do inc(i3);
d[i]:=min(d[i],d[i3]+c3);
end;
end;
procedure ans;
begin
writeln(f2,d[target]);
end;
begin
openF;
inp;
//  sort(1,n);
solve;
ans;
closeF;
end.


#### Code mẫu của ll931110

Program QBTICKET;
Const
input  = '';
output = '';
maxn = 100000;
maxl = 1000000000;
maxv = maxn * maxl;
Var
l,c: array[1..3] of longint;
heap: array[1..maxn] of longint;
a,d: array[1..maxn + 1] of int64;
n,s,f,nHeap: longint;

Procedure init;
Var
fi: text;
i,t: longint;
Begin
Assign(fi, input);
Reset(fi);

Read(fi, n, s, f);
If s > f then
Begin
t:= s;
s:= f;
f:= t;
End;

a[1]:= 0;
For i:= 2 to n do readln(fi, a[i]);
a[n + 1]:= maxv;

Close(fi);
End;

Procedure update(v: longint);
Var
child,parent: longint;
Begin
inc(nHeap);

child:= nHeap;
parent:= child div 2;

While (parent > 0) and (heap[parent] > v) do
Begin
heap[child]:= heap[parent];
child:= parent;
parent:= child div 2;
End;

heap[child]:= v;
End;

Function pop: longint;
Var
r,c,v: longint;
Begin
pop:= heap[1];
v:= heap[nHeap];
dec(nHeap);

r:= 1;
While r * 2 <= nHeap do
Begin
c:= r * 2;
If (c < nHeap) and (heap[c + 1] < heap[c]) then inc(c);

If heap[c] >= v then break;
heap[r]:= heap[c];
r:= c;
End;
heap[r]:= v;
End;

Procedure solve;
Var
i,u,v: longint;
Begin
nHeap:= 0;
For i:= 1 to n do d[i]:= maxv;
d[s]:= 0;

update(s);
Repeat
u:= pop;
v:= u;

For i:= 1 to 3 do
Begin
While (a[u] + l[i] >= a[v]) and (v <= f) do inc(v);
dec(v);

If d[v] = maxv then update(v);
If d[v] > d[u] + c[i] then d[v]:= d[u] + c[i];
End;
Until nHeap = 0;
End;

Procedure printresult;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
Writeln(fo, d[f]);
Close(fo);
End;

Begin
init;
solve;
printresult;
End.


#### Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
typedef long long ll;
ll len[3],cost[3],d[MAX];
ll f[MAX];
int n,s,t;
inline void minimize(ll &x,const ll &y) {
if (x>y) x=y;
}
void init(void) {
REP(i,3) scanf("%lld",&len[i]);
REP(i,3) scanf("%lld",&cost[i]);
scanf("%d%d%d",&n,&s,&t);
FOR(i,2,n) scanf("%lld",&d[i]);
if (s>t) swap(s,t);
}
void optimize(void) {
memset(f,0x3f,sizeof f);
f[s]=0;
int id[3];
REP(i,3) id[i]=s;
FOR(i,s+1,t) REP(j,3) {
while (id[j]<i && d[id[j]]<d[i]-len[j]) id[j]++;
if (id[j]<i) minimize(f[i],f[id[j]]+cost[j]);
}
printf("%lld",f[t]);
}
int main(void) {
init();
optimize();
return 0;
}