题目描述

题目译自 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$ 分钟内，可抵达车站的最大数目。

10 3 5
10 3 5
30
1
6
10

8

10 3 5
10 3 5
25
1
6
10

7

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

2

12 3 4
10 1 2
30
1
11
12

8

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

72

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

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$。