Tèo rất say mê trong việc giải câu đố để nhận những chiếc bánh trung thu của phường. Sau khi Tèo giựt hết bánh trung thu thì Tèo cảm thấy rất vui vẻ, nhưng niềm vui sẽ không kéo dài được bao lâu khi Tèo nhận ra đã đến giờ phải về nhà.
Khu phố Tèo đang sống có dạng như một lưới ô vuông ~n \times n~. Tèo cần di chuyển từ vị trí hiện tại có tọa độ ~(x, y)~ đến nhà Tèo là nơi có tọa độ ~(u, v)~. Trong một phút, Tèo có thể di chuyển từ nơi hiện tại đến một ô kề cạnh với ô đang đứng. Trong khu phố cũng có ~m~ điểm dịch chuyển giúp Tèo về nhà nhanh hơn, Tèo sẽ được phép dịch chuyển ngay lập tức(không tốn thời gian) đến điểm dịch chuyển nếu Tèo ở chung hàng hoặc chung cột với điểm dịch chuyển, tức là nếu Tèo đang đứng ở vị trí có tọa độ ~(a, b)~, điểm dịch chuyển có tọa độ ~(c, d)~ thì Tèo có thể đến điểm dịch chuyển ngay lập tức nếu ~a = c~ hoặc ~b = d~.
Nếu về trễ Tèo sẽ bị mẹ nhốt ngoài đường nên Tèo muốn được về nhà sớm nhất có thể. Bạn hãy giúp Tèo tìm thời gian ít nhất để Tèo có thể về đến nhà nhé!
Dữ liệu vào
- Dòng đầu tiên chứa các số nguyên dương ~n, m~ ~(1 \le n \le 10^9, 1 \le m \le 10^5)~.
- Dòng thứ hai chứa các số nguyên dương ~x, y, u, v~ lần lượt là vị trí hiện tại của Tèo và tọa độ nhà Tèo ~(1 \le x, y, u, v \le n)~.
- ~m~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương là tọa độ của các điểm dịch chuyển(các điểm dịch chuyển không trùng nhau).
Dữ liệu ra
- Một dòng duy nhất chứa một số nguyên là thời gian ngắn nhất mà Tèo có thể về đến nhà.
Ràng buộc
- Có ~30 \%~ số điểm ứng với ~n \le 10^{3}, m \le 10^{5}~.
- Có ~10 \%~ số điểm ứng với ~n \le 10^{9}, m = 0~.
- Có ~20 \%~ số điểm ứng với ~n \le 10^{9}, m \le 10^{2}~.
- Có ~20 \%~ số điểm ứng với ~n \le 10^{9}, m \le 10^{3}~.
- Còn lại ~20 \%~ số điểm không có ràng buộc gì thêm.
Ví dụ
Dữ liệu vào
5 3
1 1 5 3
2 2
3 1
4 4
Dữ liệu ra
3
Giải thích
Đường đi của Tèo: ~(1, 1) \to (3, 1) \to (4, 1) \to (4, 4) \to (5, 4) \to (5, 3)~.
~(3, 1) \to (4, 1)~ mất ~1~ phút, ~(4, 4) \to (5, 4)~ mất ~1~ phút và ~(5, 4) \to (5, 3)~ mất ~1~ phút.
Bình luận