22731번 - Data Center on Fire 스페셜 저지다국어

今から少し未来の話である．高密度記憶および長期保存可能である記録デバイスが開発されてきたが，コンテンツが生み出される速度が異常なほどに速かったため，データセンターを設立した．データセンターを設立した当初は小さな建物だったが，増え続けるデータにあわせて何度も拡張工事をしたため，性能の異なるエレベータを何基も持つこととなった．

ところが，データセンターで火災が発生した．火は一定時間だけ経過すると上の階ないし下の階に燃え広がる．また，火がついてから一定時間だけ経過するとその階は焼失してしまう．そこでエレベータを使ってデバイスを運び出すこととした．このエレベータは耐火性能が完璧であるため，階の焼失に関わらず任意の階へ移動できる．また，非常に強力な加速減速装置を持つことから，加速および減速にかかる時間は無視できるほど小さいため，一瞬にして定常速度に加速すること，あるいは停止することができる．また，緊急時においてはいわゆる「開」ボタンが機能しないようにプログラムされているため，エレベータの停止時間は運び出す（あるいは降ろす）デバイスの個数にかかわらず一定である．また，階の焼失前に到着したエレベータによって運び出されるデバイスについては，たとえエレベータの出発前に階が焼失したとしても，焼失の影響を受けない．ただし，エレベータに乗せることができなかったデバイスは当然ながら焼失する．

エレベータはどの階から回収してよいか分からないため，デバイスのある最上階を目指すようにプログラムされている．ただし，エレベータ同士は通信可能であり，別のエレベータが目的階に到着した瞬間に情報が通信される．到着したエレベータに全てのデバイスが積みこめることがわかったときは，目的階よりも下にあり，回収可能なデバイスが残っている階のうちで最上階に目的階を変更する．また，焼失のために目的階に向かう必要性が失われたときも，同様にして目的階を変更する．目的階を変更するときに，移動方向を変更する必要があるときは，即座に移動方向を変更する．また，エレベータが満杯になってそれ以上のデバイスを積みこむことができないとき，あるいは回収可能なデバイスが残っていないときは 1 階を目指す．

あなたの仕事は，上記の条件のもとで，退避させることのできたデバイスの個数および到着時刻を求めるプログラムを作成することである．

入力は複数のデータセットから構成される．それぞれのデータセットは次の形式で与えられる．

N M
d
n1 n2 ... nN
c1 v1 ts1 x1
c2 v2 ts2 x2
...
cM vM tsM xM k tx ty tz

記号の意味は次のとおりである．入力中の値はすべて整数である．

• N (2 ≤ N ≤ 30)，M (1 ≤ M ≤ 10)はそれぞれビルの階数，エレベータの基数を表す．
• d (1000 ≤ d ≤ 10000)は階と階の間の距離を表す．
• n_i (0 ≤ n_i ≤ 100) は i 階にあるデバイスの個数を表す．
• c_i (1 ≤ c_i ≤ 50)，v_i (1 ≤ v_i ≤ 2000)，ts_i (1 ≤ ts_i ≤ 20)，x_i (1 ≤ x_i ≤ N)はそれぞれ i 番目のエレベータの容量，速度，停止時間，初期位置をあらわす．初期位置は何階にあるかで表される．
• k (2 ≤ k ≤ N)，tx (30 ≤ tx ≤ 300)，ty (30 ≤ ty ≤ 300)，tz (30 ≤ tz ≤ 300)はそれぞれ火元の階，火がついてから焼失するまでの時間，上に燃え移るまでの時間，下に燃え移るまでの時間を表す．

入力の終了は 2 つの 0 を含む行によってあらわされる．これはデータセットの一部ではない．

それぞれのデータセットは次の条件を満たすと仮定してよい．

• 単位時間の 1/1000 よりも短い時間の間に複数の階の消失が起こることはない．
• 単位時間の 1/1000 よりも短い時間の間に複数のエレベータが同一の階で 1 階より上にある階に到着することない．
• 単位時間の 1/1000 よりも短い時間の間にエレベータの到着とそのエレベータが到着しようとした階の焼失が起こることはない．

それぞれのテストケースについて，回収されたデバイスの個数，および最後に回収されたデバイスが 1 階に到着してエレベータから降ろされるまでの時間を，単一の空白で区切って 1 行で出力しなさい．ただし，時間については，小数点以下に何個の数字を出力しても構わないが，0.001 を超える誤差を含めてはならない．また，1 階にあるデバイス以外は回収できなかったときは時間としてゼロを出力しなさい．