JOI 铁路是 JOI 王国唯一的铁路公司。沿铁路线共有 $N$ 个车站，编号从 $1$ 到 $N$。目前运营着两种列车：普通列车和特快列车。

普通列车在每一站都停。对于每个 $i$ ($1 \le i < N$)，乘坐普通列车从车站 $i$ 到车站 $(i + 1)$ 需要 $A$ 分钟。

特快列车仅在车站 $S_1, S_2, \dots, S_M$ ($1 = S_1 < S_2 < \dots < S_M = N$) 停靠。对于每个 $i$ ($1 \le i < N$)，乘坐特快列车从车站 $i$ 到车站 $(i + 1)$ 需要 $B$ 分钟。

JOI 铁路计划运营另一种名为“半特快”的列车。对于每个 $i$ ($1 \le i < N$)，乘坐半特快列车从车站 $i$ 到车站 $(i + 1)$ 需要 $C$ 分钟。半特快列车的停靠站尚未确定，但必须满足以下条件：

• 半特快列车必须在所有特快列车停靠的车站停靠。
• 半特快列车必须恰好在 $K$ 个车站停靠。

JOI 铁路希望最大化在 $T$ 分钟内能从车站 $1$ 到达的车站数量（不包括车站 $1$）。JOI 铁路计划确定半特快列车的停靠站，以使该数量最大化。我们不计算列车的停留时间。

当我们从车站 $1$ 前往另一个车站时，只能乘坐列车向车站编号增加的方向行驶。如果多种列车在车站 $i$ ($2 \le i \le N - 1$) 停靠，你可以在这些停靠该站的列车之间进行换乘。

在合理确定半特快列车的停靠站后，从车站 $1$ 出发在 $T$ 分钟内能到达的车站的最大数量（不包括车站 $1$）是多少？

题目描述

给定 JOI 铁路的车站数量、特快列车的停靠站、列车的速度以及最大旅行时间，编写一个程序，计算满足旅行时间条件的车站的最大数量。

输入格式

从标准输入读取以下数据。

• 第一行包含三个空格分隔的整数 $N, M, K$。这意味着 JOI 铁路有 $N$ 个车站，特快列车在 $M$ 个车站停靠，半特快列车在 $K$ 个车站停靠。
• 第二行包含三个空格分隔的整数 $A, B, C$。这意味着乘坐普通、特快、半特快列车从一个车站到下一个车站分别需要 $A, B, C$ 分钟。
• 第三行包含一个整数 $T$。这意味着 JOI 铁路希望最大化在 $T$ 分钟内能从车站 $1$ 到达的车站数量（不包括车站 $1$）。
• 接下来的 $M$ 行中的第 $i$ 行 ($1 \le i \le M$) 包含一个整数 $S_i$。这意味着特快列车在车站 $S_i$ 停靠。

输出格式

向标准输出写入一行。输出包含满足旅行时间条件的车站的最大数量。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 1\,000\,000\,000$
• $2 \le M \le K \le 3\,000$
• $K \le N$
• $1 \le B < C < A \le 1\,000\,000\,000$
• $1 \le T \le 10^{18}$
• $1 = S_1 < S_2 < \dots < S_M = N$

子任务

子任务 1 [18 分]

满足以下条件： $N \le 300$ $K - M = 2$ $A \le 1\,000\,000$ $T \le 1\,000\,000\,000$

子任务 2 [30 分]

• $N \le 300$

子任务 3 [52 分]

没有额外限制。

样例

样例输入 1

10 3 5
10 3 5
30
1
6
10

样例输出 1

8

样例输入 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