Bản đồ mê cung có dạng hình chữ nhật được chia bởi các đường song song với các cạnh tạo thành lưới ô vuông đơn vị gồm ~m~ hàng và ~n~ cột. Ô vuông nằm ở hàng ~i~ và cột ~j~ gọi là ô ~(i, j)~. Mỗi ô của mê cung có hai loại là ô tự do hoặc ô có câu hỏi. Trong mê cung có ~k~ ô có câu hỏi, người chơi đang ở một ô tự do ~(x, y)~ trong mê cung và bắt đầu di chuyển ra khỏi mê cung bằng cách đi qua các ô lân cận cạnh để đến một ô nào đó nằm ở biên của mê cung. Các câu hỏi có độ khó tăng dần được đánh số từ ~1~ đến ~k~. Trò chơi cho phép bạn mở khóa tối đa ~1~ câu hỏi và đi qua ô đó. Để đi hết một ô cần ~3~ đơn vị thời gian, để mở khóa một ô có câu hỏi cần ~1~ đơn vị thời gian. Như vậy thời gian đi hết một ô có câu hỏi cần ~4~ đơn vị thời gian. Thời gian bạn thoát khỏi mê cung là tổng thời gian đi hết ô ~(x, y)~, thời gian đi qua các ô trung gian và thời gian đi hết ô nằm ở biên.

Yêu cầu

Bạn hãy tìm hành trình thoát khỏi mê cung với tổng thời gian nhỏ nhất? Nếu có nhiều hành trình thì đưa ra hành trình mở khóa ô có câu hỏi dễ nhất.

Dữ liệu đầu vào

Gồm ~k + 1~ dòng:

• Dòng ~1~ chứa ~5~ số nguyên ~m,\ n,\ k,\ x,\ y~ ~(m, n \le 10^3,\ 0 \le k < m \times n,\ 1 < x < m,\ 1 < y < n)~;
• Trong ~k~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên dương ~u,\ v~ với ý nghĩa ở ở hàng ~u~, cột ~v~ có câu hỏi mức độ khó ~i~ ~(1 \le u \le m,\ 1 \le v \le n,\ 1 \le i \le k)~.

Dữ liệu đầu ra

• Dòng đầu tiên ghi tổng thời gian nhỏ nhất tìm được, nếu không thể thoát khỏi mê cung ghi ~-1~;
• Trong trường hợp có thể thoát khỏi mê cung, dòng hai ghi mức độ khó của câu hỏi đã sử dụng. Nếu có hành trình di chuyển không đi qua ô có câu hỏi mà vẫn đảm bảo thời gian nhỏ nhất thì ghi số ~0~.

Ràng buộc dữ liệu

• Có 30% số test ứng với 30% số điểm thỏa mãn: ~k = 0~.
• 30% số test khác ứng với 30% số điểm thỏa mãn: ~k = 1~.
• 40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

8 8 4 6 5
8 5
7 5
6 6
7 4

OUTPUT

13
2

Giải thích: Có ~4~ hành trình có thời gian ~13~ là:

1. ~(6, 5) \rightarrow (7, 5) \rightarrow (7, 6) \rightarrow (8, 6)~
2. ~(6, 5) \rightarrow (6, 6) \rightarrow (7, 6) \rightarrow (8, 6)~
3. ~(6, 5) \rightarrow (6, 6) \rightarrow (6, 7) \rightarrow (6, 8)~
4. ~(6, 5) \rightarrow (6, 4) \rightarrow (7, 4) \rightarrow (8, 4)~

Hành trình ~(6, 5) \rightarrow (7, 5) \rightarrow (7, 0) \rightarrow (8, 6)~ có câu hỏi mức độ ~2~ là nhỏ nhất.