Problem Description

Input Format

Read the following input from standard input:

• The first line contains three integers $ N, M, K $ separated by spaces. These represent that the JOI Railway has $ N $ stations, the express train stops at $ M $ stations, and the semiexpress train stops at $ K $ stations.
• The second line contains three integers $ A, B, C $ separated by spaces. These represent that the local train, express train, and semiexpress train take $ A $ minutes, $ B $ minutes, and $ C $ minutes respectively to travel between adjacent stations.
• The third line contains an integer $ T $. This represents that you want to maximize the number of stations where the total travel time from station $ 1 $ is within $ T $ minutes.
• The following $ M $ lines contain an integer $ S_i $ (for $1 \leq i \leq M$). This represents that the express train stops at station $ S_i $.

Output Format

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

Sample Input and Output

Sample Input #1

10 3 5
10 3 5
30
1
6
10

Sample Output #1

8

Sample Input #2

10 3 5
10 3 5
25
1
6
10

Sample Output #2

7

Sample Input #3

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

Sample Output #3

2

Sample Input #4

12 3 4
10 1 2
30
1
11
12

Sample Output #4

8

Sample Input #5

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

Sample Output #5

72

Sample Input #6

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

Sample Output #6

3000

Notes/Hints

Task

Given the number of stations on the JOI Railway, the stopping stations of the express train, the speeds of the trains, and the travel time condition, create a program to find the maximum number of stations that satisfy the travel time condition.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [18 points]

Satisfies the following conditions:

• $N \leq 300$.
• $ K - M = 2 $.
• $A \leq 1,000,000$.
• $T \leq 1,000,000,000$.

Subtask 2 [30 points]

• $N \leq 300$.

Subtask 3 [52 points]

• No additional constraints.

Sample Explanation 1

In this input example, the JOI Railway has $ 10 $ stations, and the express train stops at $ 3 $ stations: $ 1, 6, 10 $. If the semiexpress train stops at stations $ 1, 5, 6, 8, 10 $, you can travel to $ 8 $ out of the $ 9 $ stations (excluding station $ 9 $) within $ 30 $ minutes from station $ 1 $. Here are some examples of travel times and methods for some stations:

• From station $ 1 $ to station $ 3 $, you can travel using only the local train in $ 20 $ minutes.
• From station $ 1 $ to station $ 7 $, you can travel by express train to station $ 6 $ and then switch to the local train for a total of $ 25 $ minutes.
• From station $ 1 $ to station $ 8 $, you can travel by express train to station $ 6 $ and then switch to the semiexpress train for a total of $ 25 $ minutes.
• From station $ 1 $ to station $ 9 $, you can travel by express train to station $ 6 $, then by semiexpress train to station $ 8 $, and finally by local train to station $ 9 $ for a total of $ 35 $ minutes.

Sample Explanation 2

Sample Explanation 3

Sample Explanation 4

This input example does not satisfy the conditions of Subtask $ 1 $.

Sample Explanation 5

This input example does not satisfy the conditions of Subtask $ 1 $.

Sample Explanation 6

This input example does not satisfy the conditions of Subtask $ 1 $ or Subtask $ 2 $.

见题面 Input 部分

见题面 Output 部分