17742번 - Bus Tour 서브태스크다국어

JOI 市では公共交通機関が発達している．特に，バス専用道路が碁盤目状に敷き詰められているので，バ スは交通状況の影響を受けることなく，一定の速度で運行することができる．南北方向のバス専用道路は 1km 間隔で W 本あり，東西方向のバス専用道路は 1km 間隔で H 本ある．すべてのバスは，長方形の形を した経路上を時計回りに 1 分あたり 1km の速度走る．また，バス専用道路が交わる点にバス停が設置され ている．

JOI 君は今日，クリケットの試合を観戦しに行く予定であったが，寝坊してしまった．もう試合開始には 間に合わないかもしれないが，JOI 君はできるだけ長い間試合を観戦していたいので，できるだけ早く試 合会場に到着したい．

JOI 君は，バスの運行情報を事前に調べていたので，バスの現在地と，それぞれのバスの運行経路はわ かっている．今すぐ出発して，バスを乗り継いでいったとき，会場に到着するまでにかかる最短時間を求 めるプログラムを書け．ただし，移動はバスを使ってのみ行うものとし，バスからバスへの乗り継ぎには 時間がかかるので，バスを降りた瞬間に同じ交差点にいるバスに即座に乗り換えることはできず，降りて から 1 分後以降に到着したバスに乗ることのみできるとする．また，JOI 君がバスのみをつかって会場ま でたどり着けることは保証されている．

標準入力から以下の入力を読み込め．

• 1 行目には 6 つの整数 W, H, S_X, S_Y, G_X, G_Y (1 ≤ S_X ≤ W かつ 1 ≤ S_Y ≤ H かつ 1 ≤ G_X ≤ W かつ 1 ≤ G_Y ≤ H) がこの順に空白で区切られて書かれている．これは，南北方向のバス専用道路が W 本 通っており，それに直交する東西方向のバス専用道路が H 本通っていることを意味する．また，JOI 君ははじめ，西から S_X 番目のバス専用道路と，北から S_Y 番目のバス専用道路の交差する場所に居 て，JOI 君の目的地である試合会場は，西から G_X 番目のバス専用道路と，北から G_Y 番目のバス専 用道路の交差する場所にある．JOI 君の初期位置は，JOI 君の目的地とは異なる．また，JOI 君が出 発した瞬間には，JOI 君の初期位置にバスがあることはない．
• 2 行目には JOI 市で運行されているバスの本数を表す 1 つの整数 N が書かれている．
• 続く N 行には，バスの情報が書かれている．N 行のうちの i 行目には，5 つの整数 X1_i , Y1_i , X2_i , Y2_i , T_i (1 ≤ X1_i < X2_i ≤ W かつ 1 ≤ Y1_i ≤ Y2_i ≤ H かつ 0 ≤ T < 2 × (X2_i − X1_i + Y2_i − Y1_i) ) が書かれてい る．これは，i 番目のバスの経路の北西端は，西から X1i 番目のバス専用道路と，北から Y1_i 番目の バス専用道路の交差するところであり，i 番目のバスの経路の南東端は，西から X2_i 番目のバス専用 道路と，北から Y2_i 番目のバス専用道路の交差するところであることを表している．また，JOI 君が 出発した時点で，i 番目のバスは，その経路上を北西端から時計回りに T_i km だけ進んだ位置にいる．

JOI 君が出発してから，試合会場に到着するまでにかかる時間の最小値を 1 行で出力せよ．

• 2 ≤ W ≤ 1 000．
• 2 ≤ H ≤ 1 000．
• 1 ≤ N ≤ 1 000．

• W ≤ 30．
• H ≤ 30．
• N ≤ 30．

• W ≤ 300．
• H ≤ 300．
• N ≤ 300．

追加の制限はない．