B - 準急電車 (Semiexpress) 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

配点： 100 点

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

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

急行電車は M 個の駅 S_1, S_2, \ldots, S_M (1 = S_1 < S_2 < \cdots < S_M = N) に停車する．また，各 i (1 \leqq i < N) について，駅 i と駅 i + 1 の間を B 分で走行する．

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

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

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

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

出力

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

制限

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

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

小課題

小課題 1 [18 点]

以下の条件を満たす．

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

小課題 2 [30 点]

  • N \leqq 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, \ldots, 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 の条件を満たさない．