B-准高速电车_JOI2017-Final比赛真题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题目译自 JOI 2017 Final T2「準急電車 / Semiexpress」

JOI铁路公司是JOI国唯一的铁路公司。
在某条铁路沿线共有N座车站，依次编号为 $1 \ldots N$ 。目前，正在服役的车次按照运行速度可分为两类：高速电车（简称快车）与普通电车（简称慢车）。

慢车每站都停。乘慢车时，对于任意一座车站 $i(1 \leqslant i \lt N)$ ，车站i到车站i+1用时均为A。
快车只在车站 $S_1,S_2, \ldots,S_M$ 停车 $(1=S_1 \lt S_2 \lt \cdots \lt S_M=N)$ 。乘快车时，对于任意一座车站 $i(1 \leqslant i \lt N)$ ，车站i到车站i+1用时均为B。JOI铁路公司现拟开设第三类车次：准高速电车（简称准快车）。乘准快车时，对于任意一座车站 $i(1 \leqslant i \lt N)$ ，车站i到车站i+1用时均为C。准快车的停站点尚未确定，但满足以下条件：

快车在哪些站停车，准快车就得在哪些站停车。

准快车必须恰好有K个停站点。
JOI铁路公司希望，在T分钟内（不含换乘时间），车站1可以抵达的车站（不含车站1）的数量尽可能多。但是，「后经过的车站的编号」必须比「先经过的车站的编号」大。

求出在T分钟内，可抵达车站的最大数目。

输入描述:

第一行有三个整数N,M,K，用空格分隔。
第二行有三个整数A,B,C，用空格分隔。
第三行有一个整数T。
在接下来的M行中，第i行有一个整数。
输入的所有数的含义见题目描述。

输出描述:

一行，一个整数，表示在$T$分钟内，可抵达车站的最大数目。

示例1

输入

复制

输出

复制

说明

在这组样例中，这条铁路上有10个车站，快车在车站1,6,10停车。如果准快车在车站1,5,6,8,10停车，除车站⑨外的其它所有车站都可在30分钟内到达。
以下是从地点1到达某些站点的最快方案：
到达车站3：乘坐慢车，耗时20分钟。
到达车站7：先乘坐快车，在车站6转慢车，耗时25分钟。
到达车站8：先乘坐快车，在车站6转准快车，耗时25分钟。
到达车站⑨：先乘坐快车，在车站6转准快车，在车站8再转慢车，耗时35分钟。

示例2

输入

复制

输出

复制

示例3

输入

复制

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

输出

复制

示例4

输入

复制

输出

复制

示例5

输入

复制

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300

输出

复制

示例6

输入

复制

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

输出

复制

备注:

对于的数据，。
对于另外的数据，。
对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自https://loj.ac/problem/2333