Thành phố hiện đại meLona, nơi Sơn sinh sống, được quy hoạch thành một mạng lưới giao thông dạng lưới vuông góc. Thành phố có kích thước ~W \times H~, với ~W~ tuyến đường dọc từ Bắc xuống Nam (đánh số từ ~1~ đến ~W~, từ Tây sang Đông), và ~H~ tuyến đường ngang từ Đông sang Tây (đánh số từ ~1~ đến ~H~, từ Bắc xuống Nam). Giao điểm giữa một đường dọc và một đường ngang được gọi là nút giao thông, ký hiệu là ~(u, v)~.

Hệ thống vận tải công cộng ở meLona bao gồm các tàu lửa tự động, chạy liên tục quanh các khu vực dân cư theo các tuyến đường hình chữ nhật, theo chiều kim đồng hồ. Mỗi tàu chạy không ngừng theo chu kỳ trên một chu vi hình chữ nhật cố định.

Có tổng cộng ~N~ tuyến tàu lửa như vậy. Tuyến thứ ~i~ chạy quanh hình chữ nhật có góc trên bên trái là ~(X_{1i}, Y_{1i})~ và góc dưới bên phải là ~(X_{2i}, Y_{2i})~. Vào thời điểm ~0~, tàu ~i~ đã bắt đầu hành trình từ đỉnh ~(X_{1i}, Y_{1i})~ và đã chạy được ~T_i~ đơn vị thời gian.

Sơn cần đi từ nhà ở vị trí ~(X_S, Y_S)~ đến trường tại vị trí ~(X_T, Y_T)~. Sơn chỉ được phép di chuyển bằng tàu lửa và có thể lên hoặc xuống tàu tại bất kỳ thời điểm nào tàu đi qua nút mà Sơn đang đứng. Tuy nhiên, sau khi xuống một tàu tại thời điểm ~t~, Sơn chỉ có thể lên một tàu khác bắt đầu từ thời điểm ~t + 1~ trở đi.

Hãy tính thời gian nhanh nhất để Sơn có thể đến được trường.

Input

Dòng đầu tiên chứa sáu số nguyên ~W, H, X_S, Y_S, X_T, Y_T~ ~(1 \leq X_S, X_T \leq W \leq 1000,\ 1 \leq Y_S, Y_T \leq H \leq 1000)~.

Dòng thứ hai chứa số nguyên dương ~N~ ~(1 \leq N \leq 1000)~ ~-~số tuyến tàu lửa.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~5~ số nguyên: ~X_{1i}, Y_{1i}, X_{2i}, Y_{2i}, T_i~, mô tả hành trình tàu ~i~.

Các điều kiện đảm bảo: ~1 \leq X_{1i}, X_{2i} \leq W~ , ~1 \leq Y_{1i}, Y_{2i} \leq H~ ~0 \leq T_i < 2 \times (|X_{2i} - X_{1i}| + |Y_{2i} - Y_{1i}|)~

Output

In ra một số nguyên duy nhất là thời gian sớm nhất Sơn có thể đến trường.

Subtask

Subtask ~1~ (~25\%~ số điểm): ~1 \leq W, H, N \leq 30~.

Subtask ~2~ (~25\%~ số điểm): ~1 \leq W, H, N \leq 300~.

Subtask ~3~ (~25\%~ số điểm): ~1 \leq W, H, N \leq 500~.

Subtask ~4~ (~25\%~ số điểm): không có ràng buộc nào thêm.

Sample Input

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

Sample Output

50