#2333. 「JOI 2017 Final」准高速电车

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 JOI 2017 Final T2「準急電車 / Semiexpress

JOI 铁路公司是 JOI 国唯一的铁路公司。

在某条铁路沿线共有 N 座车站,依次编号为 1\ldots N 。 目前,正在服役的车次按照运行速度可分为两类:高速电车(简称快车)与普通电车(简称慢车)。

  • 慢车每站都停。乘慢车时,对于任意一座车站 i(1\leqslant i<N) ,车站 i 到车站 i+1 用时均为 A
  • 快车只在车站 S_1, S_2, \ldots, S_M 停车 (1=S_1<S_2<\cdots<S_M=N) 。乘快车时,对于任意一座车站 i(1\leqslant i<N) ,车站 i 到车站 i+1 用时均为 B

JOI 铁路公司现拟开设第三类车次:准高速电车(简称准快车)。乘准快车时,对于任意一座车站 i(1\leqslant i<N) ,车站 i 到车站 i+1 用时均为 C 。准快车的停站点尚未确定,但满足以下条件:

  • 快车在哪些站停车,准快车就得在哪些站停车。
  • 准快车必须恰好有 K 个停站点。

JOI 铁路公司希望,在 T 分钟内(不含换乘时间),车站 1 可以抵达的车站(不含车站 1 )的数量 尽可能多。但是,「后经过的车站的编号」必须比「先经过的车站的编号」大

求出在 T 分钟内,可抵达车站的最大数目。

输入格式

第一行有三个整数 N, M, K ,用空格分隔。
第二行有三个整数 A, B, C ,用空格分隔。
第三行有一个整数 T
在接下来的 M 行中,第 i 行有一个整数 S_i
输入的所有数的含义见题目描述。

输出格式

一行,一个整数,表示在 T 分钟内,可抵达车站的最大数目。

样例

样例输入 1

10 3 5
10 3 5
30
1
6
10

样例输出 1

8

样例解释 1

在这组样例中,这条铁路上有 10 个车站,快车在车站 1, 6, 10 停车。如果准快车在车站 1, 5, 6, 8, 10 停车,除车站⑨外的其它所有车站都可在 30 分钟内到达。
以下是从地点 1 到达某些站点的最快方案:

  • 到达车站 3 :乘坐慢车,耗时 20 分钟。
  • 到达车站 7 :先乘坐快车,在车站 6 转慢车,耗时 25 分钟。
  • 到达车站 8 :先乘坐快车,在车站 6 转准快车,耗时 25 分钟。
  • 到达车站 9 :先乘坐快车,在车站 6 转准快车,在车站 8 再转慢车,耗时 35 分钟。

样例输入 2

10 3 5
10 3 5
25
1
6
10

样例输出 2

7

样例输入 3

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

样例输出 3

2

样例输入 4

12 3 4
10 1 2
30
1
11
12

样例输出 4

8

样例输入 5

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300

样例输出 5

72

样例输入 6

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

样例输出 6

3000

数据范围与提示

对于 18\% 的数据, N\leqslant 300, K-M=2, A\leqslant 10^6, T\leqslant 10^9
对于另外 30\% 的数据, N\leqslant 300
对于所有数据, 1\leqslant N\leqslant 10^9, 2\leqslant M\leqslant K\leqslant 3000, K\leqslant N, 1\leqslant B<C<A\leqslant 10^9, 1\leqslant T\leqslant 10^{18}, 1=S_1<S_2<\cdots<S_M=N