Khu đô thị mới ở phía Nam thành phố Đà Nẵng được quy hoạch dạng lưới gồm trên một khu vực kích thước \(W \times H\). Có \(W\) con đường chạy theo hướng Bắc Nam (đánh số từ \(1\) đến \(W\) từ Tây sang Đông) và \(H\) con đường chạy theo hướng Đông Tây (đánh số từ \(1\) đến \(H\) từ Bắc xuông Nam). Giao lộ của con đường dọc thứ \(u\) và con đường ngang thứ \(v\) được gọi là nút \((u, v)\).

Khu vực này có \(N\) tuyến xe buýt. Lộ trình của mỗi tuyến xe buýt đều tạo thành một hình chữ nhật, thuận chiều kim đồng hồ. Tuyến thứ \(i\) có lộ trình là hình chữ nhật với góc trái trên là nút \((X_{1i}, Y_{1i})\), góc phải dưới là nút \((X_{2i}, Y_{2i})\).

Tại thời điểm \(0\), Thái cần di chuyển từ nhà ở vị trí \((X_{S}, Y_{S})\) đến trường là vị trí \((X_{T}, Y_{T})\). Lúc
này xe buýt thứ \(i\) đã đi qua vị trí \((X_{1i}, Y_{1i})\) một khoảng cách là \(T_{i}\). Bạn hãy giúp Thái xác định thời gian nhanh nhất để có mặt ở trường. Lưu ý rằng Thái có thể sử dụng nhiều tuyến xe buýt. Khi Thái xuống xe buýt ở thời điểm \(t\), Thái có thể lên chuyến xe buýt khác nếu chuyến xe buýt đó đến ở thời điểm \(t + 1\) trở đi.

Input

• Dòng đầu tiên chứa sáu số nguyên dương \(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)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo, mỗi dòng chứa \(5\) số nguyên dương \(X_{1i}, Y_{1i}, X_{2i}, Y_{2i}, T_{i}\) \((1 \leq X_{1i}, X_{2i} \leq W, 1 \leq Y_{1i}, Y_{2i} \leq H, 0 \leq T_{i} < 2 × (|X_{2i} − X_{1i}| + |Y_{2i} − Y_{1i}|))\).

Output

• In ra duy nhất một số nguyên là thời gian sớm nhất mà Thái có mặt ở trường. Dữ liệu đảm bảo luôn có cách chỉ di chuyển bằng xe buýt để tới được trường.

Scoring

• 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.

Example

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

50

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

6