問題文

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

普通電車はすべての駅に停車し，各 $i$ ($1 \leq i < N$) について，駅 $i$ と駅 $i + 1$ の間を $A$ 分で走行する． 急行電車は $M$ 個の駅 $S_1, S_2, ..., S_M$ ($1 = S_1 < S_2 < ... < S_M = N$) に停車する．また，各 $i$ ($1 \leq i < N$) について，駅 $i$ と駅 $i + 1$ の間を $B$ 分で走行する．

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

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

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

ただし，JOI 鉄道を用いて駅 $1$ から他の駅まで移動するときは，駅の番号が大きくなる方向の電車しか用いることができない．また，駅 $i$ ($2 \leq i \leq 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 \leq i \leq M$) には，整数 $S_i$ が書かれている．これは，急行電車が駅 $S_i$ に停車することを表す．

出力

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

10 3 5
10 3 5
30
1
6
10

8

10 3 5
10 3 5
25
1
6
10

7

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

2

12 3 4
10 1 2
30
1
11
12

8

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

72

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

3000

制限

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

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

小課題

小課題 1 [18 点] $\quad$ $N ≦ 300,$ $K − M = 2,$ $A ≦ 10^6,$ $T ≦ 10^9$ を満たす．
小課題 2 [30 点] $\quad$ $N ≦ 300$ を満たす．
小課題 3 [52 点] $\quad$ 追加の制限はない．