题目描述

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$，表示快车停的站点。

输出格式

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

样例解释 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(\texttt{18 pts})$

$N\leq 3000,K-M=2,A\leq 10^6,T\leq 10^9$

子任务 $2(\texttt{30 pts})$

$N\leq 300$

子任务 $3(\texttt{52 pts})$

无特殊限制。