Semiexpress

Time Limit : 1 sec, Memory Limit : 262144 KB

準急電車(Semiexpress)

JOI 国の唯一の鉄道会社であるJOI 鉄道には1 本の線路に沿って $N$ 個の駅があり,順に 1, 2, ... , $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 行で出力せよ.

制限

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

  • $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 < ... < S_M = N$

入出力例

入力例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

入力例5

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

出力例5

72

入力例5

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

出力例5

3000

Source: 16th Japanese Olympiad in Informatics , 2016-2-11
http://www.ioi-jp.org/