题目描述

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

在某条铁路沿线共有 $n$ 个站点，依次编号为 $1,2,\cdots, n$。当前有两种列车服役，分别是高速列车和普通列车。

• 普通列车每站都停，对于每一个 $i(1\leq i < N)$，从站点 $i$ 到站点 $i+1$ 用时 $A$ 分钟。

• 高速列车只在站点 $S_1,S_2,\cdots,S_M(1=S_1<S_2<\cdots<S_M=N)$ 停车，对于每一个 $i(1\leq i < N)$，从站点 $i$ 到站点 $i+1$ 用时 $B$ 分钟。

JOI 铁路公司拟定开设第三类车次：准高速列车。对于每一个 $i(1\leq i < N)$，从站点 $i$ 到站点 $i+1$ 用时 $C$ 分钟。准高速列车停的站点还没有决定好，但是这些站点必须满足以下要求：

• 高速列车停的所有站点准高速列车都必须停。

• 准高速列车必须停恰好 $K$ 个站点。

JOI 铁路公司想要最大化从 $1$ 号站点在 $T$ 分钟内可以到的站点数目（不计 $1$ 号站点，不计等车和换乘时间），JOI 铁路公司想要合理地安排站点使得这个数目最大。

当合理地安排准高速列车停的站点时，从 $1$ 号站点出发在 $T$ 分钟内抵达的站点（$1$ 号站点不计）最多是多少？

输入格式

第一行三个整数 $N,M,K$，意义如题面所示。

第二行三个整数 $A,B,C$，意义如题面所示。

第三行一个整数 $T$，意义如题面所示。

接下来 $M$ 行，这 $M$ 行中的第 $i$ 行有一个整数 $S_i$，表示快车停的站点。

输出格式

一行一个整数，表示答案。

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

6

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

提示

【样例解释】

对于样例 $1$，一共有 $10$ 个站点，快车停 $1,6,10$ 三个站点。我们假设准快车停 $1,5,6,8,10$ 五个站点，于是，在 $2,3,\cdots,10$ 中，我们可以从 $1$ 号站点在 $30$ 分钟内抵达除了 $9$ 号站点的所有站点。

对于某些 $i$，从 $1$ 号站点到 $i$ 号站点最优的方案如下：

• 从 $1$ 号站点到 $3$ 号站点，只需要乘坐普通列车，时间为 $20$ 分钟。

• 从 $1$ 号站点到 $7$ 号站点，先乘坐高速列车到站点 $6$，然后转乘普通列车，时间为 $25$ 分钟。

• 从 $1$ 号站点到 $8$ 号站点，先乘坐高速列车到站点 $6$，然后转乘准高速列车，时间为 $25$ 分钟。

• 从 $1$ 号站点到 $9$ 号站点，先乘坐高速列车到站点 $6$，然后转乘准高速列车到站点 $8$，再换乘普通列车，时间为 $35$ 分钟。

【数据范围与约定】

所有的数据满足以下条件：

• $2\leq N\leq 10^9,2\leq M\leq K\leq 3000,K\leq N$。

• $1\leq B < C < A \leq 10^9,1\leq T\leq 10^{18}$。

• $1=S_1<S_2<\cdots<S_M=N$。

1. Subtask $1$（$18$ pts）：$N\leq 3000,K-M=2,A\leq 10^6,T\leq 10^9$。

2. Subtask $2$（$30$ pts）：$N\leq 300$。

3. Subtask $3$（$52$ pts）：无特殊限制。