Thành phố JOI có hệ thống giao thông công cộng phát triển. Các đường dành riêng cho xe buýt tạo thành một lưới: có \(W\) đường chạy theo hướng bắc–nam và \(H\) đường chạy theo hướng đông–tây, các đường liên tiếp cùng hướng cách nhau \(1\) km. Mỗi giao điểm là một trạm xe buýt. Tất cả xe buýt chạy theo chiều kim đồng hồ trên một tuyến hình chữ nhật, với tốc độ không đổi \(1\) km mỗi phút.

JOI định đi xem một trận cricket nhưng đã ngủ quên. Cậu muốn đến sân thi đấu càng sớm càng tốt để xem được nhiều nhất có thể. Cậu đã biết tuyến đường và vị trí hiện tại của từng xe buýt.

Đánh số các đường bắc–nam từ tây sang đông và các đường đông–tây từ bắc xuống nam. Giao điểm của đường thứ \(x\) và đường thứ \(y\) có tọa độ \((x,y)\). Ban đầu JOI ở \((S_X,S_Y)\), còn sân thi đấu ở \((G_X,G_Y)\).

JOI chỉ được di chuyển bằng xe buýt. Việc chuyển xe cần thời gian: nếu xuống một xe tại thời điểm \(t\), cậu không thể lên ngay một xe khác đang ở cùng giao điểm tại thời điểm đó; cậu chỉ có thể lên xe đến trạm từ thời điểm \(t+1\) trở đi. Bảo đảm có thể đến sân thi đấu chỉ bằng xe buýt.

Yêu cầu

Hãy tính thời gian ít nhất, tính bằng phút kể từ hiện tại, để JOI đến sân thi đấu bằng cách đi và chuyển các xe buýt.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa sáu số nguyên \(W,H,S_X,S_Y,G_X,G_Y\).
• Dòng thứ hai chứa số nguyên \(N\), là số xe buýt.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa năm số nguyên \(X1_i,Y1_i,X2_i,Y2_i,T_i\). Tuyến của xe thứ \(i\) có góc tây bắc tại \((X1_i,Y1_i)\) và góc đông nam tại \((X2_i,Y2_i)\). Tại thời điểm ban đầu, xe ở vị trí cách góc tây bắc \(T_i\) km khi đi theo chiều kim đồng hồ dọc theo tuyến.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa thời gian ít nhất để JOI đến sân thi đấu.

Ràng buộc

• Giới hạn thời gian: 3 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(2\le W,H\le1000\).
• \(1\le N\le1000\).
• \(1\le S_X,G_X\le W\) và \(1\le S_Y,G_Y\le H\).
• Vị trí ban đầu khác đích đến. Tại thời điểm ban đầu, không có xe buýt nào ở vị trí của JOI.
• \(1\le X1_i<X2_i\le W\) và \(1\le Y1_i\le Y2_i\le H\).
• \(0\le T_i<2(X2_i-X1_i+Y2_i-Y1_i)\).
• Bảo đảm JOI có thể đến đích chỉ bằng xe buýt.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (30 điểm): \(W,H,N\le30\).
• Nhóm 2 (50 điểm): \(W,H,N\le300\).
• Nhóm 3 (20 điểm): Không có ràng buộc bổ sung.

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

50

Ban đầu JOI phải chờ xe số \(1\). Cậu lên xe này sau \(10\) phút; đến phút thứ \(11\), cậu đang ở \((2,3)\). Cậu xuống xe số \(1\) ở \((5,5)\) vào phút thứ \(16\). Đến phút thứ \(19\), cậu vẫn chờ ở trạm này trong khi xe số \(2\) ở \((7,9)\). Cậu lên xe số \(2\) tại \((5,5)\) vào phút thứ \(27\).

Sau đó, JOI xuống xe số \(2\) ở \((7,5)\) vào phút thứ \(29\). Đúng lúc này xe số \(3\) cũng ở cùng giao điểm, nhưng cậu không thể lên xe đó ngay vì việc chuyển xe cần \(1\) phút. Cậu chờ đến phút thứ \(43\) để lên xe số \(3\). Vào phút thứ \(49\), cậu ở \((9,1)\) và đến sân thi đấu sau đó \(1\) phút. Không có cách đến sớm hơn, nên kết quả là \(50\).

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

6