You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

提示

【样例解释】

对于样例 $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）：无特殊限制。