なつめは大のねこ好きである。なつめの通学路には通称ねこ屋敷と呼ばれている家がある。その家はたくさんのねこを飼っていることで有名で、なつめは通学途中によくこの家の前で飼いねこに遭遇し、一緒に遊んでいた。そんなある日、なつめは衝撃的な事実を知ってしまった。それは、実はねこ屋敷の主人は、機嫌が悪くなるとよく飼いねこたちを虐待している、ということだった。ねこ屋敷の主人を許せなくなったなつめは、ねこたちを救うため、主人の居ない間にねこたちを盗みだすことにした。
なつめはねこ屋敷の主人の行動パターンを観察し、毎週決まって出掛けているタイミングをねらってねこたちを盗みだすことにした。ねこ屋敷は二次元平面として表わされており、なつめが屋敷の中に忍びこむ時点でのそれぞれのねこの位置は分かっている。ねこたちはそれぞれ決まったルートを常に50メートル毎分のスピードでまわっている。一方、なつめは最大80メートル毎分のスピードで移動できる。なつめは屋敷のとある場所から侵入し、屋敷内を移動し、主人が帰ってくるまでに脱出口から出る。なつめがねこと同じ地点に到達すると、なつめはねこを抱えることができる。これを行なうのにかかる時間は無視できる。なつめは何匹でもねこを抱えることができるし、何匹抱えていても移動速度が落ちることはないが、必ず主人が帰ってくる前に屋敷を脱出しなければならない。
残念ながら、なつめはねこ屋敷のねこを全員盗みだすことはできないかもしれない。しかし、1匹でも多くのねこを幸せにするために、できるだけ多くのねこを盗みだすことにした。また、同じ数のねこを盗みだせるのであれば、屋敷の主人に捕まるリスクを抑えるため、できるだけ早い時間に屋敷から脱出する。
なつめが屋敷に侵入する時刻と位置、屋敷の主人が戻ってくる時刻、脱出口の場所、およびねこの初期位置と巡回ルートが与えられる。なつめが何匹のねこを盗みだして、どの時刻に屋敷を脱出できるかを答えるプログラムを書いてほしい。
入力の1行目には、侵入口の x, y 座標が1つの空白文字で区切られて与えられる。2行目には同様に脱出口の位置が与えられる。3行目にはなつめが屋敷に侵入した時刻、4行目には屋敷の主人が帰ってくる時刻が24時間制のHH:MM:SSの形式で与えられる。
5行目はねこの総数 m であり、続く m 行に各ねこの行動パターンが与えられる。5+i 行目 (i = 1, 2, ..., m) が i 番目のねこの巡回ルートに対応している。各行の初めには自然数 ki が与えられ、続いてねこの巡回ルートが ki 個の x, y 座標値を並べたものとして与えられる。ねこの巡回ルートは、これらの連続する点および最後と最初の点を線分でつないだものである。なつめが屋敷に侵入した時点で、ねこは与えられた最初の点におり、以降ずっと巡回ルート上を等速で移動する。与えられたルートの連続する点が同じ座標であることはない。
なお、スタート時間とゴール時間は同じ日でのものであることが保証されている．なつめが主人の帰ってくる前に脱出する方法は必ず存在する。同じ行にある数は全て1つの空白文字で区切られている。
ねこの数は1以上14以下、ねこの巡回ルートを表わす点の数は2以上1000以下であり、全ての座標値は絶対値が100000を越えない整数であることが保証されている。 座標値の単位は全てメートルである。
1行目に、なつめが盗み出すことのできるねこの最大数を出力せよ。2行目には、なつめがなるべく多い数のねこを盗みだす方法の中で、最も早く脱出口に到達できる時刻を、HH:MM:SS.nnnnnn の形式で答えよ。秒の小数点以下は6桁出力せよ。なお、10-6 秒を越える誤差があってはならない。
なお、主人の帰ってくる時間が±1ms変化しても、最多遭遇可能数は変化しないことが保証されている。
0 0 0 0 15:00:00 18:00:00 1 4 0 7199 1125 7199 1125 8324 0 8324
0 0 0 0 15:00:00 18:00:00 1 4 0 7201 1125 7201 1125 8326 0 8326
1 17:59:59.076923
0 15:00:00.000000