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$ 分で走行する.準急電車の停車駅は決まっていないが,以下の条件を満たすようにすることは決まっている.
JOI 鉄道は,駅1 から1 種類以上の電車を使って移動するときの乗車時間の合計が $T$ 分以内となるような,駅1 以外の駅の個数が最大となるように準急電車の停車駅を決めることにした.ここで,乗車時間には停車時間は含めないものとする.
ただし,JOI 鉄道を用いて駅1 から他の駅まで移動するときは,駅の番号が大きくなる方向の電車しか用いることができない.また,駅 $i$ ($2 \leq i \leq N - 1$) に複数の種別の電車が停車するとき,その駅では停車するすべての電車に乗り換えることができる.
準急電車の停車駅をうまく決めたときの,駅1 からの乗車時間の合計が $T$ 分以内となるような,駅1 以外の駅の個数の最大値を求めたい.
JOI 鉄道の駅の個数,急行電車の停車駅,電車の速度の情報,乗車時間の条件が与えられたとき,乗車時間の条件を満たす駅の個数の最大値を求めるプログラムを作成せよ.
標準入力から以下の入力を読み込め.
標準出力に,乗車時間の条件を満たす駅の個数の最大値を1 行で出力せよ.
すべての入力データは以下の条件を満たす.
10 3 5 10 3 5 30 1 6 10
8
この入力例では,JOI 鉄道には10 個の駅があり,急行電車は3 個の駅1, 6, 10 に停車する.準急電車を駅1, 5, 6, 8, 10 に停車させると,駅2, 3, ... , 10 のうち駅9 を除く8 個の駅に,駅1 から30 分以内の乗車時間で移動できる.
準急電車の停車駅を上記のように決めたときの,いくつかの $i$ についての,駅1 から駅 $i$ まで移動する際の乗車時間と,そのときの移動方法を示す.
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