시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 1 1 1 100.000%

문제

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

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

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

입력

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

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

출력

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

제한

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

예제 입력 1

10 10 1 3 10 1
3
1 3 5 6 4
5 5 7 10 1
7 1 10 5 9

예제 출력 1

50

上の図はこの入力例において JOI 市を上空から見た図である.丸印は,バスの現在地を表している.矢 印が,そのバスの経路を表している.JOI 君の現在地は三角形で示されており,目的地である試合会場は 四角形で示されている.

JOI 君は,1 番のバスが来るまで待たなければいけない.10 分後に 1 番のバスに乗り込んだとすると,11 分後の状態は次のようになる.

続いて,JOI 君は 1 番のバスから 2 番のバスへ乗り換える必要がある.出発から 16 分後に JOI 君がバス を下車したとすると,19 分後の状態は次のようになる.

2 番のバスに乗ったあと,3 番のバスに乗り換える.出発から 29 分後,JOI 君が 2 番のバスを下車した とすると,そのとき,同じ交差点に 3 番のバスが停車している.しかし,乗り換えには 1 分の時間を要す るので,このバスに乗ることはできない.

出発から 43 分後,JOI 君が 3 番のバスに乗ったとすると,試合会場に到着する直前の 49 分後の様子は 次のようになる.

この 1 分後,JOI 君は試合会場に到着する.これよりも早く到着することはできないので,プログラム は 50 を出力する.

예제 입력 2

4 3 2 1 4 3
3
1 1 4 2 0
1 1 2 2 3
2 2 4 3 3

예제 출력 2

6