54階建てのビルに、22人乗りのエレベータが一機ある。
このエレベータは、人数に関係なく一回の乗降に10秒かかり、1階あたり1秒の速度で昇降する。

a 秒時点で b 階に c 階へ行きたい ddd さんが来るという情報を、

a, b, c, ddd

というcsv形式で与える。このデータは時刻aで昇順にソートされており、同時に二人の人物が来た場合は2行に分けられる。

これを元に、入力に出現した全員を目的の階に降ろすまでのエレベータの昇降と人物の乗降を、各人の所要時間
の合計が最小になるようにスケジューリングし、e 秒時点に f 階で ggg, hhh, iii さ
んが乗降するというデータを

e, f, ggg, hhh, iii

という形式で出力せよ。 e は乗降開始の時刻であり、同時に乗降する人物は一列にまとめよ。出力は e で昇順にソートせよ。同一人物は出力の中に二度出現し、一度目は乗車、二度目は降車を表す必要がある。

回答フォームには、規定された出力と、各人の所要時間の合計を入力せよ。

なお、各変数の定義域と値域は次の通りである.

  * 時点をあらわす a, e は、スケジュール開始時点を 0 とする非負の整数である.
    値域は、 [1, 1000000] の範囲である。(スケジュール開始と同時には人は来ない)
  * 階をあらわす b, c, fは、1階を1, 54階を54とする正の整数である. 値域は
    [1, 54] である。
  * 人物を表す ddd, ggg, hhh, iii は、asciiのアルファベット小文字3つで構成
    される三文字の文字列である。 aaa, aab, ... ,zzz の値をとる。

また、詳細な条件は以下の通りである。

  * 入力には、同一人物は一度しか出現しない。
  * 出力では、同一人物を必ず二回出現させる必要がある。目的の階に到着するとは
    目的の階で降車することであり、出発階以外の階からの乗車や目的階以外の階への
    降車は認めない。
  * スケジューリング開始時点 (時刻 0[sec]) に、エレベータは1階で、すぐに移動可能
    な状態で待機している。 (たとえば、時刻 3[sec] に 3階 で乗降を開始することが出来る)
  * 乗降は、乗降終了時点 (=移動開始時点) まで可能である。

    たとえば、20[sec] 時点に 10階に出現する abc が、 10[sec] 時点に
    10 階で乗降を開始したエレベータに乗車し、30[sec] 時点で 20 階で
    降車することが可能である。この場合、abcの所要時間とは、降車時点の30
    から出現時点の20[sec]を引いた10[sec]になる。

データ: schedule.csv 

1, 16, 1, aaa
20, 20, 10, aab
75, 1, 6, aac
101, 15, 1, aad
127, 13, 1, aae
156, 13, 1, aaf
185, 4, 1, aag
213, 17, 10, aah
226, 1, 7, aai
286, 1, 5, aaj
302, 16, 10, aak
373, 8, 18, aal
432, 13, 1, aam
498, 12, 10, aan
573, 13, 1, aao
解説はこちらとなります。