Maximizing Reachable Stations

Aqours Railway Company has N stations numbered from 1 to N. There are two pre‐existing train types:

• Local trains that stop at every station and take A minutes to run between any two consecutive stations.
• Express trains that only stop at the M forced stops S₁,S₂,… ,S_M (with \(S_1=1\) and \(S_M=N\)) and take B minutes between two consecutive express stops (note: when “consecutive” here we mean in the express stopping order, not station‐by‐station).

Now a new rapid train is being introduced. It has the following properties:

• It must stop exactly at K stations (with \(K > M\)); its stopping stations R (sorted increasingly) must include all forced stops \(S_1, S_2, \dots, S_M\).
• The rapid train runs at constant speed such that it takes C minutes between any two consecutive stations in its stopping sequence.

Passengers are allowed to transfer between any trains (i.e. if more than one train stops at a station, they may change) and may only travel forward (i.e. from a lower‐numbered station to a higher‐numbered station). Note that waiting times for transfer or for the train to depart are not counted – only riding time matters.

The goal is to design a stopping plan for the rapid train (i.e. choose the additional K−M stops arbitrarily among stations {1,2,…,N} as long as all forced stops are included) so that the number of stations that can be reached from station 1 within a total ride time of T minutes is maximized. (A station is considered reached if there exists a sequence of rides and transfers, using any combination of the three train types, that takes no more than T minutes in total.)

For any station, a passenger may choose to use one of the following routes:

1. Local route: Ride the local train directly. The time is \((j-1)\times A\) minutes to reach station \(j\).
2. Express route: Ride the express train from station 1 (forced) to the last forced stop \(S_i\) not exceeding \(j\), then transfer to the local train to go from \(S_i\) to \(j\). The time is \((i-1)\times B + (j-S_i)\times A\) minutes.
3. Rapid route: Using the rapid train route. If the forced stop \(S_i\) is the last forced stop \(\le j\), then in the interval from \(S_i\) to \(j\) one may add extra stops. However, because the rapid train must stop at exactly K stations overall, there is a limit on how many extra stops can be inserted after \(S_i\). In particular, if we have already used \(i\) forced stops then at most \(K-i\) extra stops may be added between \(S_i\) and \(j\). In an optimal design the minimum achievable riding time along the rapid route is given by:
   
   \(t_{rapid}(j)=\begin{cases}\;(i-1+(j-S_i))\times C, &\text{if } (j-S_i) \le K-i,\\[6mm] (K-1)\times C + (j-S_i-(K-i))\times A, &\text{otherwise.}\end{cases}\)

Thus the minimum time to reach station \(j\) is the minimum of the three times:

[ f(j)=\min\Big{ (j-1),A,; (i-1),B+(j-S_i),A,; t_{rapid}(j) \Big}, ]

where \(S_i\) is the largest forced stop \(\le j\) (i.e. if \(S_i \le j < S_{i+1}\)). Since these functions are increasing in \(j\), the set of stations that can be reached from station 1 within time \(T\) is \(\{1,2,\dots, X\}\), where \(X\) is the largest \(j\) with \(f(j) \le T\).

Your task is to compute and output \(X\) given the input values.

inputFormat

The input consists of two lines. The first line contains seven integers: N M K T A B C.

The second line contains M integers: S₁ S₂ … S_M, the forced express stops (with \(S_1=1\) and \(S_M=N\)).

Note: It is guaranteed that \(K > M\).

outputFormat

Output a single integer representing the maximum number of stations (starting from station 1) that can be reached within T minutes of riding time.

sample

10 2 5 15 2 1 1
1 10

10