题意描述

JOI 铁路公司是 JOI 国唯一的铁路公司。

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

慢车每站都停。乘慢车时，对于任意一座车站 $i(1\leqslant i<N)$，车站 $i$ 到车站 $i+1$ 用时均为 $A$。
快车只在车站 $S_1, S_2, \ldots, S_M$ 停车 $(1=S_1<S_2<\cdots<S_M=N)$。

乘快车时，对于任意一座车站 $i(1\leqslant i<N)$，车站 $i$ 到车站 $i+1$ 用时均为 $B$。

JOI 铁路公司现拟开设第三类车次：准高速电车（简称准快车）。乘准快车时，对于任意一座车站 $i(1\leqslant i<N)$，车站 $i$ 到车站 $i+1$ 用时均为 $C$。准快车的停站点尚未确定，但满足以下条件：

快车在哪些站停车，准快车就得在哪些站停车。
准快车必须恰好有 $K$ 个停站点。

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

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

输入格式

第一行有三个整数 $N, M, K$，用空格分隔。

第二行有三个整数 $A, B, C$，用空格分隔。

第三行有一个整数 $T$。

在接下来的 $M$ 行中，第 $i$ 行有一个整数 $S_i$。

输入的所有数的含义见题目描述。

输出格式

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

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围和约定

对于 $30\%$ 的数据，$N\leqslant 300, K-M=2, A\leqslant 10^6, T\leqslant 10^9$。

对于另外 $40\%$ 的数据，$N\leqslant 300$。

对于所有数据，$1\leqslant N\leqslant 10^9, 2\leqslant M\leqslant K\leqslant 3000, K\leqslant N, 1\leqslant B<C<A\leqslant 10^9, 1\leqslant T\leqslant 10^{18}, 1=S_1<S_2<\cdots<S_M=N$。

分析

比较好想的贪心，但不太好写。

对于一个位置，我们到达它必定是快车 -> 准快车 -> 慢车，其中三段都可以为空。

而题目中给出的快车点刚好将总路程分成了 $m$ 段以快车开头的路程，故可以单独对每一段路程进行思考。

考虑什么情况下我们会在该位置设立准快车站？

显然，在坐慢车 $T$ 时刻内能到的点设立准快车站对答案没有贡献。而节省的时间越多对后面越有利。

故我们在坐慢车能到的下一个点放置准快车站，之后重复上述过程即可。

时间复杂度为 $O(km)$。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

ll n , m , K;
ll A , B , C;
ll T , S[5005] , Z[5005] , cnt , ans;

#define LOCAL 

int main() {
    #ifdef LOCAL
        freopen("car.in" , "r" , stdin);
        freopen("car.out" , "w" , stdout);
    #endif
    read(n) , read(m) , read(K);
    read(A) , read(B) , read(C);
    read(T);
    rep(i , 1 , m) read(S[i]);
   
    vector<ll> Z;
    rep(i , 2 , m) {
        ll tim = (S[i - 1] - 1) * B;
        if(tim > T) break;
        ll dis = (T - tim) / A;
        ans += min(S[i] - S[i - 1] - 1 , dis);
        if(dis > S[i] - S[i - 1]) continue;
        ll  pla = S[i - 1] + min(S[i] - S[i - 1] - 1 , (T - tim) / C) , tims = 0;
        int p = S[i - 1] + dis + 1;
        while(p <= pla) {
            ll tmp = (T - tim - (p - S[i - 1]) * C) / A;
            tmp = min(tmp , S[i] - p - 1);
            Z.pb(tmp + 1);
            p += tmp + 1;
            tims ++;
            if(tims + m >= K) break;
        }
    }
    rep(i , 2 , m) {
        if((S[i] - 1) * B <= T) ans ++;
    }
    if(Z.size() == 0) return printf("%lld\n" , ans) , 0;
    else {
        sort(all(Z));
        per(i , (int)Z.size() - 1 , 0) {
            if(K > m) K -- , ans += Z[i];
        }
    }
    printf("%lld\n" , ans);

    return 0;
}