B - 準急電車 (Semiexpress)

Time Limit: 1 sec / Memory Limit: 256 MB

配点 : 100

JOI 国の唯一の鉄道会社である JOI 鉄道には 1 本の線路に沿って N 個の駅があり,順に 1, 2, ... , N の番号が付いている.現在,運行されている電車の種別は,急行普通の 2 種類である.

普通電車はすべての駅に停車し,各 i (1 ≦ i \lt N) について,駅 i と駅 i + 1 の間を A 分で走行する.

急行電車は M 個の駅 S_1, S_2, ... , S_M (1 = S_1 \lt S_2 \lt … \lt S_M = N) に停車する.また,各 i (1 ≦ i \lt N) について,駅 i と駅 i + 1 の間を B 分で走行する.

JOI 鉄道は電車の種別として準急電車を新設することにした.準急電車は各 i (1 ≦ i \lt N) について,駅 i と駅 i + 1 の間を C 分で走行する.準急電車の停車駅は決まっていないが,以下の条件を満たすようにすることは決まっている.

  • 準急電車はすべての急行停車駅に停車する.
  • 準急電車はちょうど K 個の駅に停車する.

JOI 鉄道は,駅 1 から 1 種類以上の電車を使って移動するときの乗車時間の合計が T 分以内となるような,駅 1 以外の駅の個数が最大となるように準急電車の停車駅を決めることにした.ここで,乗車時間には停車時間は含めないものとする.

ただし,JOI 鉄道を用いて駅 1 から他の駅まで移動するときは,駅の番号が大きくなる方向の電車しか用いることができない.また,駅 i (2 ≦ i ≦ N - 1) に複数の種別の電車が停車するとき,その駅では停車するすべての電車に乗り換えることができる.

準急電車の停車駅をうまく決めたときの,駅 1 からの乗車時間の合計が T 分以内となるような,駅 1 以外の駅の個数の最大値を求めたい.

課題

JOI 鉄道の駅の個数,急行電車の停車駅,電車の速度の情報,乗車時間の条件が与えられたとき,乗車時間の条件を満たす駅の個数の最大値を求めるプログラムを作成せよ.


入力

標準入力から以下の入力を読み込め.

  • 1 行目には,3 個の整数 N, M, K が空白を区切りとして書かれている.これらは,JOI 鉄道に駅が N 個あり,急行電車は M 個の駅に停車し,準急電車は K 個の駅に停車することを表す.
  • 2 行目には,3 個の整数 A, B, C が空白を区切りとして書かれている.これらは,普通電車,急行電車,準急電車が隣り合う駅の間を走行するのにかかる時間がそれぞれ A 分,B 分,C 分であることを表す.
  • 3 行目には,整数 T が書かれている.これは,駅 1 からの乗車時間の合計が T 分以内となる駅の個数を最大化したいことを表す.
  • 続く M 行のうちの i 行目 (1 ≦ i ≦ M) には,整数 S_i が書かれている.これは,急行電車が駅 S_i に停車することを表す.

出力

標準出力に,乗車時間の条件を満たす駅の個数の最大値を 1 行で出力せよ.


制限

すべての入力データは以下の条件を満たす.

  • 2 ≦ N ≦ 1\,000\,000\,000
  • 2 ≦ M ≦ K ≦ 3\,000
  • K ≦ N
  • 1 ≦ B \lt C \lt A ≦ 1\,000\,000\,000
  • 1 ≦ T ≦ 10^{18}
  • 1 = S_1 \lt S_2 \lt ・ ・ ・ \lt S_M = N

小課題

小課題 1 [18 点]

以下の条件を満たす.

  • N ≦ 300
  • K - M = 2
  • A ≦ 1\,000\,000
  • T ≦ 1\,000\,000\,000

小課題 2 [30 点]

  • N ≦ 300 を満たす.

小課題 3 [52 点]

  • 追加の制限はない.

入力例 1

10 3 5
10 3 5
30
1
6
10

出力例 1

8

この入力例では,JOI 鉄道には 10 個の駅があり,急行電車は 3 個の駅 1, 6, 10 に停車する.準急電車を駅 1, 5, 6, 8, 10 に停車させると,駅 2, 3, ... , 10 のうち駅 9 を除く 8 個の駅に,駅 1 から 30 分以内の乗車時間で移動できる.

準急電車の停車駅を上記のように決めたときの,いくつかの i についての,駅 1 から駅 i まで移動する際の乗車時間と,そのときの移動方法を示す.

  • 1 から駅 3 へは,普通電車だけを用いて 20 分の乗車時間で移動できる.
  • 1 から駅 7 へは,駅 1 から駅 6 まで急行電車で移動し,駅 6 で普通電車に乗り換えることで 25 分の乗車時間で移動できる.
  • 1 から駅 8 へは,駅 1 から駅 6 まで急行電車で移動し,駅 6 で準急電車に乗り換えることで 25 分の乗車時間で移動できる.
  • 1 から駅 9 へは,駅 1 から駅 6 まで急行電車で移動し,駅 6 から駅 8 まで準急電車で移動し,駅 8 から駅 9 まで普通電車で移動することで 35 分の乗車時間で移動できる.

入力例 2

10 3 5
10 3 5
25
1
6
10

出力例 2

7

入力例 3

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

出力例 3

2

入力例 4

12 3 4
10 1 2
30
1
11
12

出力例 4

8

この入力例は,小課題 1 の条件を満たさない.


入力例 5

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

出力例 5

72

この入力例は,小課題 1 の条件を満たさない.


入力例 6

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

出力例 6

3000

この入力例は,小課題 1 および小課題 2 の条件を満たさない.

Score : 100 points

The JOI Railways is the only railway company in the Kingdom of JOI. There are N stations numbered from 1 to N along a railway. Currently, two kinds of trains are operated; one is express and the other one is local.

A local train stops at every station. For each i (1 \leq i \lt N), by a local train, it takes A minutes from the station i to the station (i + 1).

An express train stops only at the stations S_1, S_2, ..., S_M (1 = S_1 \lt S_2 \lt ・・・ \lt S_M = N). For each i (1 \leq i \lt N), by an express train, it takes B minutes from the station i to the station (i + 1).

The JOI Railways plans to operate another kind of trains called “semiexpress.” For each i (1 \leq i \lt N), by a semiexpress train, it takes C minutes from the station i to the station (i + 1). The stops of semiexpress trains are not yet determined. But they must satisfy the following conditions:

  • Semiexpress trains must stop at every station where express trains stop.
  • Semiexpress trains must stop at K stations exactly.

The JOI Railways wants to maximize the number of stations (except for the station 1) to which we can travel from the station 1 within T minutes. The JOI Railways plans to determine the stops of semiexpress trains so that this number is maximized. We do not count the standing time of trains.

When we travel from the station 1 to another station, we can take trains only to the direction where the numbers of stations increase. If several kinds of trains stop at the station i (2 ≦ i ≦ N - 1), you can transfer between any trains which stop at that station.

When the stops of semiexpress trains are determined appropriately, what is the maximum number of stations (except for the station 1) to which we can travel from the station 1 within T minutes?

Task

Given the number of stations of the JOI Railways, the stops of express trains, the speeds of the trains, and maximum travel time, write a program which calculates the maximum number of stations which satisfy the condition on the travel time.


Input

Read the following data from the standard input.

  • The first line of input contains three space separated integers N, M, K. This means there are N stations of the JOI Railways, an express train stops at M stations, and a semiexpress train stops at K stations,
  • The second line of input contains three space separated integers A, B, C. This means it takes A, B, C minutes by a local, express, semiexpress train to travel from a station to the next station, respectively.
  • The third line of input contains an integer T. This means the JOI Railways wants to maximize the number of stations (except for the station 1) to which we can travel from the station 1 within T minutes.
  • The i-th line (1 ≦ i ≦ M) of the following M lines contains an integer S_i . This means an express train stops at the station S_i .

Output

Write one line to the standard output. The output contains the maximum number of stations satisfying the condition on the travel time.


Constraints

All input data satisfy 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 \lt C \lt A \leq 1\,000\,000\,000.
  • 1 \leq T \leq 10^{18} .
  • 1 = S_1 \lt S_2 \lt ・・・ \lt S_M = N.

Subtask

Subtask 1 [18 points]

The following conditions are satisfied.

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

Subtask 2 [30 points]

  • N \leq 300.

Subtask 3 [52 points]

There are no additional constraints.


Sample Input 1

10 3 5
10 3 5
30
1
6
10

Sample Input 1

10 3 5
10 3 5
30
1
6
10

Sample Output 1

8

In this sample input, there are 10 stations of the JOI Railways. An express train stops at three stations 1, 6, 10. Assume that the stops of an semiexpress train are 1,5,6,8,10. Then, among the stations 2,3,...,10, we can travel from the station 1 to every station except for the station 9 within 30 minutes.

For some i, the travel time and the route from the station 1 to the station i are as follows:

  • From the station 1 to the station 3, we can travel using a local train only. The travel time is 20 minutes.
  • From the station 1 to the station 7, we travel from the station 1 to the station 6 by an express train, and transfer to a local train. The travel time is 25 minutes.
  • From the station 1 to the station 8, we travel from the station 1 to the station 6 by an express train, and transfer to a semiexpress train. The travel time is 25 minutes.
  • From the station 1 to the station 9, we travel from the station 1 to the station 6 by an express train, from the station 6 to the station 8 by a semiexpress train, and from the station 8 to the station 9 by a local train. In total, the travel time is 35 minutes.

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

This sample input does not satisfy the constrains of Subtask 1.


Sample Input 5

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

Sample Output 5

72

This sample input does not satisfy the constrains of Subtask 1.


Sample Input 6

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

Sample Output 6

3000

This sample input does not satisfy the constrains of Subtask 1. Also, this sample input does not satisfy the constrains of Subtask 2.