Trò chơi với mê cung

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

Một 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 chung 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.

Input

• 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\)). Các ô có câu hỏi đôi một khác nhau và khác ô \((x, y)\).

Ràng buộc:

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

Output

• 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 thì 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\).

Example

Input:

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

Output:

13
2

Note

Có \(4\) hành trình có thời gian \(13\): \((6,5) \to (7,5) \to (7,6) \to (8,6)\) (dùng câu hỏi ở ô \((7,5)\), mức \(2\)); \((6,5) \to (6,6) \to (7,6) \to (8,6)\) và \((6,5) \to (6,6) \to (6,7) \to (6,8)\) (dùng câu hỏi ở ô \((6,6)\), mức \(3\)); \((6,5) \to (6,4) \to (7,4) \to (8,4)\) (dùng câu hỏi ở ô \((7,4)\), mức \(4\)). Mỗi hành trình đi qua \(4\) ô gồm một ô câu hỏi (\(4\) đơn vị) và ba ô tự do (\(3\) đơn vị mỗi ô), tổng \(13\). Mức độ khó nhỏ nhất là \(2\), nên đáp án là \(13\) và \(2\).