Trong thế giới tương lai, khoa học vũ trụ phát triển vượt bậc, việc di chuyển và khám phá giữa các hành tinh không còn là điều khó khăn đối với con người. Huy, một phi hành gia tài ba, đang điều khiển một robot thám hiểm trên hành tinh X. Bản đồ của hành tinh có dạng một bản đồ dạng lưới có ~n~ hàng và ~m~ cột. Các hàng được đánh số liên tiếp từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số liên tiếp từ ~1~ đến ~m~ từ trái sang phải, ô nằm trên hàng ~i~ và cột ~j~ của bản đồ có một giá trị nguyên dương ~a[i, j]~, đại diện cho mức độ nguy hiểm tại ô ~(i, j)~.

Robot của Huy hiện tại đang đứng ở ô ~(s, t)~, cần di chuyển từ vị trí hiện tại đến vị trí của căn cứ đặt tại ô ~(u, v)~. Do địa hình của hành tinh X khá phức tạp, giả sử robot của Huy hiện tại đang ở ô ~(i, j)~, robot chỉ có thể di chuyển bằng một trong hai cách sau:

• Di chuyển sang một trong bốn ô kề cạnh. Cụ thể hơn, từ ô ~(i, j)~ robot của Huy có thể di chuyển sang một trong bốn ô ~(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)~ nếu ô tiếp theo vẫn nằm trong bản đồ, chi phí năng lượng cho lần di chuyển này là ~a[i, j]~.
• Robot của Huy có khả năng dịch chuyển qua các ô khác, bằng cách sử dụng ~Q~ khoảng dịch chuyển có dạng ~(L_x, R_x)~ (~1 \le x \le Q~). Lưu ý rằng, ~Q~ khoảng dịch chuyển này đôi một không giao nhau, nghĩa là với mọi ~x, y~ sao cho ~x \neq y~, thì ~R_x < L_y~ hoặc ~L_x > R_y~. Ô ~(i, j)~ được gọi là thuộc khoảng dịch chuyển ~x~ khi và chỉ khi ~L_x \le a[i, j] \le R_x~. Robot có thể dịch chuyển từ ô ~(i, j)~ sang ô ~(i', j')~ nếu ô ~(i, j)~ và ô ~(i', j')~ thuộc cùng một khoảng dịch chuyển, chi phí năng lượng cho một lần dịch chuyển là ~w~.

Yêu cầu: Hãy xác định con đường có tổng chi phí năng lượng nhỏ nhất để robot đi từ ~(s, t)~ đến ~(u, v)~.

Input

• Dòng đầu tiên gồm 4 số nguyên không âm ~n, m, Q, w~ (~1 \le n, m \le 1500, 0 \le Q \le 10^5, 1 \le w \le 10^6~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên dương ~a[i, j]~ (~1 \le a[i, j] \le 10^6~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L_x~ và ~R_x~ (~1 \le L_x \le R_x \le 10^6~).
• Dòng cuối cùng chứa bốn số nguyên ~s, t, u, v~ (~1 \le s, u \le n, 1 \le t, v \le m~).

Output

• Một dòng duy nhất ghi một số là chi phí năng lượng ít nhất để robot của Huy có thể đi từ vị trí xuất phát đến vị trí của căn cứ.