配点: 100 点
JOI铁路,该国唯一的铁路公司,拥有 1 沿着铁轨 有 N 个站,按顺序 它们的编号最大为 1, 2, \ldots, N 。目前运营的列车类型有: 有两种类型:急行和 按字典顺序比较普通。
本地列车在所有车站停靠。 i (1 \leqq i < N) 关于车站 i 和车站 i + 1 运行时间为 A 分钟。
特快列车是 M 站 停在 S_1, S_2, \ldots, S_M (1 = S_1 < S_2 < \cdots < S_M = N处)。另外,每个 i (1 \leqq i < N) 关于车站 i 和车站 i + 1 运行时间为 B 分钟。
JOI铁路是火车的一种。 我们决定新成立準急電車。每趟半快车 运行时间为 i (1 \leqq i < N) 关于车站 i 和车站 i + 1 运行时间为 C 分钟。虽然半快车的停靠站尚未确定,但已确定满足以下条件。
- 半快车在所有快车站停靠。
- 半快车就在 它停在 K 站。
JOI铁路是一个车站 1 减去 1 乘坐多于一种类型的火车旅行时的总乘坐时间为 T 分钟内到达的车站 我们决定决定半快车停靠的车站,以便最大限度地增加 1 以外的车站数量。这里,骑行时间不包括停车时间。
但是,如果使用 JOI 铁路 从 1 前往其他车站时,只能乘坐车站编号增加方向的列车。还有,车站 当多种车种停靠 i (2 \leqq i \leqq N - 1)时,您可以转乘该站停靠的所有列车。
您已成功决定在哪里停靠半快车时的车站。 从 1 开始的总骑行时间为 我想找到除 T 分钟内到达的车站 我们决定决定半快车停靠的车站,以便最大限度地增加 1 之外的最大站数。
課題
JOI 给定火车站数量、快车停靠站、列车速度信息和乘车时间条件,编写程序找出满足乘车时间条件的最大车站数量。
入力
从标准输入读取以下输入。
- 1 行中, 请输出第3 整数 给出了 N, M, K 以空格作为分隔符。这些车站位于 JOI 铁路上。 N 有,而且特快列车是 半快车停靠在 M 站。 代表停在 K 站。
- 2 行中, 请输出第3 整数 给出了 A, B, C 以空格作为分隔符。这些是普通列车、快速列车和半快速列车在相邻车站之间运行的时间。 代表 A 分,B 分,C 分钟。
- 3 第行写入整数 T 。这是车站 1 开始的总骑行时间为 我想找到除 T 表示您希望在几分钟内最大化电台数量。
- 继续 M 行 i 行目 (1 \leqq i \leqq M) 包含整数 S_i 。这是车站的特快列车。 表示停在 S_i 。
出力
满足乘车时间条件的最大站数设置为标准输出。 1 请以行的形式输出。
制限
所有输入数据满足以下条件。
- 2 \leqq N \leqq 1\,000\,000\,000.
- 2 \leqq M \leqq K \leqq 3\,000.
- K \leqq N.
- 1 \leqq B < C < A \leqq 1\,000\,000\,000.
- 1 \leqq T \leqq 10^{18}.
- 1 = S_1 < S_2 < \cdots < S_M = N.
小課題
小課題 1 [18 点]
满足以下条件。
- N \leqq 300.
- K - M = 2.
- A \leqq 1\,000\,000.
- T \leqq 1\,000\,000\,000.
小課題 2 [30 点]
- N \leqq 300 很满意。
小課題 3 [52 点]
- 没有其他限制。
入力例 1
10 3 5 10 3 5 30 1 6 10
出力例 1
8
在此输入示例中,JOI 铁路有 有 10 站,特快列车有 停在 3 站 停在 1, 6, 10 。车站的半快车 如果您停在 1, 5, 6, 8, 10 ,车站 2, 3, \ldots, 10 内站 排除 9 除了 8 站,站 您可以在 1 减去 30 分钟内到达。
当半快车停靠站如上确定后,有以下几种: 关于 i ,该站 这显示了骑行时间以及如何前往 1 从车站 i 。 要前往
- 駅 1 从车站 3 ,请仅乘坐当地火车。 仅需 20 分钟即可抵达。
- 駅 1 从车站 7 到车站 乘坐特快列车到 1 从车站 6 站下车。 在 6 换乘慢车 在 25 分钟即可抵达。
- 駅 1 从车站 8 到车站 乘坐特快列车到 1 从车站 6 站下车。 在 6 换乘半快车 乘坐半快车到 25 分钟即可抵达。
- 駅 1 从车站 9 到车站 乘坐特快列车到 1 从车站 6 站下车。 在 6 从车站 8 站下车。 乘坐当地火车前往 8 从车站 9 乘坐当地火车前往 35 分钟即可抵达。
入力例 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
这个输入示例是 不满足条件 1 。
入力例 5
300 8 16 345678901 123456789 234567890 12345678901 1 10 77 82 137 210 297 300
出力例 5
72
这个输入示例是 不满足条件 1 。
入力例 6
1000000000 2 3000 1000000000 1 2 1000000000 1 1000000000
出力例 6
3000
这个输入示例是 不满足条件 1 和小作业 不满足 2 。