問題
山田君はHOJ高校に通う２年生。彼は、頭脳明晰、スポーツ万能、おまけに絵に描いたようなイケメンっぷりである。
しかし、そんな彼にも１つだけ弱点がある。そう、彼は学校一の方向音痴なのだ。
彼の友達には、とても変人がいる。名前は、杉浦尚人。尚人は、毎朝の山田君の登校時間を彼が家をでた瞬間から学校に着くまでを見守り、計っている。
しかし、尚人は委員会の用事で今日の時間を計ることができない。
そこで、尚人は地域の範囲、家の座標と学校の座標、工事現場の数とその座標が書き込まれた地図を特別に用意した。その地図を利用して、山田君が学校に着くまでにかかる最長と最短の時間を算出してほしい。
今日は各所で工事が行われているため、地図に明記してあるその場所は通れない。
地域は図のようにマス目状になっており、マス目の１辺を移動するのにかかる時間を１とする。
※・地域の範囲は左下(1,1)から右上(w,h)とし、どんな場合でも必ず学校に到着できるものとする。
・ルートは複数個ある場合がある。
・家から学校までの間、一度通った地点は通れないものとする。
入力
w,h sx,sy,gx,gy n x1,y1 x2,y2 ・ ・ ・ xn,yn
入力は以下のようになる。 区切り文字','が' 'でないことに注意しよう。
1行目 地域の範囲 "横(w),縦(h)"
2行目 家の座標(sx,sy) 学校の座標(gx,gy) 例) 1,1,5,4
3行目 工事現場の数n
4+i行目 工事現場の座標i(x[i],y[i]) 例)1,1
4+n-1行目 工事現場の座標n-1(x[n-1],y[n-1])
出力
家を出てから学校に到着する最長と最短の時間を以下のように出力する。最短時間 最長時間
制約
全ての入出力ケースについて以下を満たす。
- h×w ≦ 64 , n≦62
入出力例
入力例1
5,4 1,1,5,4 3 2,2 2,3 4,2 5,5 1,5,3,3 10 2,2 3,2 4,2 2,3 4,3 2,4 2,5 3,5 4,5 5,5 0,0
出力例1
7 15 14 14