Semiexpress

Time limit1sMemory limit256 MB

Summary

Choose exactly K stops for a new train so that the number of stations reachable from station 1 within T minutes is maximized.

Level: Hard8 of 10
Topics: Greedy, Binary search, Prefix sum
Solved: No attempts yet

Problem

JOI Railways is the only railway company in the Kingdom of JOI. There are $N$ stations along one railway line, numbered from $1$ to $N$ . Two kinds of trains currently run on the line: express trains and local trains.

A local train stops at every station. For each $i$ ( $1 \le i < N$ ), a local train takes $A$ minutes to go from station $i$ to station $i+1$ .

An express train stops only at stations $S_1, S_2, \ldots, S_M$ ( $1 = S_1 < S_2 < \cdots < S_M = N$ ). For each $i$ ( $1 \le i < N$ ), an express train takes $B$ minutes to go from station $i$ to station $i+1$ .

JOI Railways plans to run a new kind of train called a semiexpress. For each $i$ ( $1 \le i < N$ ), a semiexpress train takes $C$ minutes to go from station $i$ to station $i+1$ . The stops of the semiexpress train are not decided yet, but they must satisfy these conditions:

The semiexpress train stops at every station where the express train stops.
The semiexpress train stops at exactly $K$ stations.

JOI Railways wants to choose the semiexpress stops so that the number of stations (not counting station $1$ ) that can be reached from station $1$ within $T$ minutes is as large as possible. The time a train spends standing at a station is not counted.

When traveling from station $1$ to another station, you may only ride trains in the direction of increasing station numbers. If several kinds of trains stop at station $i$ ( $2 \le i \le N-1$ ), you can transfer between any of the trains that stop there.

Write a program that computes the maximum number of stations (not counting station $1$ ) reachable from station $1$ within $T$ minutes when the semiexpress stops are chosen optimally.

Input

Read the following data from standard input.

The first line contains three space-separated integers $N, M, K$ : there are $N$ stations, the express train stops at $M$ stations, and the semiexpress train stops at $K$ stations.
The second line contains three space-separated integers $A, B, C$ : a local, express, and semiexpress train takes $A$ , $B$ , and $C$ minutes respectively to go from one station to the next.
The third line contains an integer $T$ : the goal is to maximize the number of stations (not counting station $1$ ) reachable from station $1$ within $T$ minutes.
The $i$ -th of the next $M$ lines ( $1 \le i \le M$ ) contains an integer $S_i$ : the express train stops at station $S_i$ .

Output

Print one line to standard output containing the maximum number of stations that satisfy the travel time condition.

Constraints

All input data satisfy the following conditions.

$2 \le N \le 1\,000\,000\,000$
$2 \le M \le K \le 3\,000$
$K \le N$
$1 \le B < C < A \le 1\,000\,000\,000$
$1 \le T \le 10^{18}$
$1 = S_1 < S_2 < \cdots < S_M = N$

Examples6

Example 1
Input
```
10 3 5
10 3 5
30
1
6
10
```
Expected output
```
8
```
Example 2
Input
```
10 3 5
10 3 5
25
1
6
10
```
Expected output
```
7
```

Example 3

Input

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

Expected output

Example 4
Input
```
12 3 4
10 1 2
30
1
11
12
```
Expected output
```
8
```

Example 5

Input

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

Expected output

Example 6

Input

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

Expected output