← 返回题目列表

AtCoder · joi2017ho_b

B. 半快递

中文机器翻译题面 查看原题

配点: 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 。