问题 3519 --火车票

3519: 火车票

题目描述

  一个铁路线上有n(2<=n<=10000)个火车站,每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下表所示:
站之间的距离 - X      票价
0<X<=L1       C1
L1<X<=L2 C2
L2<X<=L3 C3
其中L1,L2,L3,C1,C2,C3都是已知的正整数,且(1 <= L1 < L2 < L3 <= 10^9, 1 <= C1 < C2 < C3 <= 10^9)。显然若两站之间的距离大于L3,那么从一站到另一站至少要买两张票。注意:每一张票在使用时只能从一站开始到另一站结束。
现在需要你对于给定的线路,求出从该线路上的站A到站B的最少票价。你能做到吗?

输入

输入文件的第一行为6个整数,  L1,  L2,  L3,  C1,  C2,  C3  (1  < =  L1  <   L2  <   L3  < =  10^9,  1  < =  C1  <   C2  <   C3  < =  10^9)  ,这些整数由空格隔开.第二行为火车站的数量N  (2  < =  N  < =  10000).第三行为两个不同的整数A、B,由空格隔开。接下来的  N-1  行包含从第一站到其他站之间的距离.这些距离按照增长的顺序被设置为不同的正整数。相邻两站之间的距离不超过L3.  两个给定火车站之间行程花费的最小值不超过10^9,而且任意两站之间距离不超过  10^9。

输出

输出文件中只有一个数字,表示从A到B要花费的最小值. 

样例输入输出

输入#1 复制
3 6 8 20 30 40
7
2 6
3
7
8
13
15
23
输出#1 复制
70

提示

序号 标题 作者 发表时间 费用 订购数 操作