Description

Aqours Railway Company has $N$ stations, numbered 1, 2, ..., $N$.

There are two types of trains: Local (stops at every station) and Express. The express train stops at $S_1, S_2, ..., S_M$ ($1 = S_1 < S_2 < ... < S_M = N$), for a total of $M$ stations.

Between two adjacent stations (i.e., the station numbered $i$ and the station numbered $i+1$, not two consecutive express stops), the local takes $A$ minutes and the express takes $B$ minutes. We assume trains run at constant speed, ignoring dwell times and acceleration/deceleration.

Now we add a new Rapid train. It must include all express stops among its stops, and it takes $C$ minutes to travel between two adjacent stations. To be faster, it will stop at exactly $K$ stations ($K > M$), including all express stations. If a station is served by multiple train types, passengers can transfer at that station. However, they can only travel forward, not backward.

You need to design a stopping pattern for the rapid train so that, within $T$ minutes of in-train time (waiting and transfer times are not counted), a passenger starting from station 1 can reach as many stations as possible. You only need to report how many stations can be reached.

Input Format

The first line contains three integers $N$, $M$, $K$, as described above.

The second line contains three integers $A$, $B$, $C$, as described above.

The third line contains one integer $T$, the riding time.

Then $M$ lines follow, each containing one integer. The $i$-th integer is $S_i$.

Output Format

Output a single integer, the maximum number of stations that can be reached within the time limit.

10 3 5
10 3 5
30
1
6
10

8

Hint

[Sample explanation]

You can set the rapid stops to be 1/5/6/8/10.

Stations 2, 3, 4 can be reached directly by taking the local. Station 5 can be reached by taking the rapid. Stations 6 and 10 can be reached by taking the express. Station 7 can be reached by transferring at 6 to the local, and station 8 can be reached by transferring at 6 to the rapid. Station 9 cannot be reached within 30 minutes of riding time.

Constraints

• For 20% of the testdata, $N \le 300$, $K - M = 2$, $A \le 10^6$, $T \le 10^9$.
• For 50% of the testdata, $N \le 1000$.
• For 100% of the testdata, $2 \le N \le 10^9$, $2 \le M \le K \le 3000$, $1 \le B < C < A \le 10^9$, $1 \le T \le 10^{18}$.

Translated by ChatGPT 5