Trong một khu vực có lưới ô vuông, mỗi ô có một độ cao. Xe chỉ được đi sang một ô kề cạnh (trên, dưới, trái hoặc phải). Nếu xe đi từ ô có độ cao a sang ô có độ cao b, thời gian di chuyển là |a - b|.

Xe tuần tra bắt đầu ở ô (x_1, y_1), có T đơn vị nhiên liệu. Xe tiếp nhiên liệu bắt đầu ở ô (x_2, y_2) và không bị giới hạn nhiên liệu. Quán mì Udon nằm ở ô (x_3, y_3).

Hai xe bắt đầu di chuyển tại thời điểm 0; trong mỗi tọa độ (x, y), x là hàng và y là cột.

Cả hai xe có thể dừng chờ tại một ô. Thời gian chờ được tính vào thời gian đến quán nhưng không tiêu hao nhiên liệu. Xe tuần tra tiêu hao nhiên liệu bằng đúng thời gian di chuyển. Khi hai xe cùng dừng tại một ô, xe tiếp nhiên liệu có thể nạp thêm D đơn vị nhiên liệu cho xe tuần tra ngay lập tức. Việc nạp nhiên liệu được thực hiện nhiều nhất một lần; xe tuần tra có thể được nạp kể cả khi đã hết nhiên liệu.

Trong lúc di chuyển giữa hai ô, xe không được xem là đang đứng trên ô nào. Vì vậy, hai xe chỉ có thể tiếp nhiên liệu khi cùng đứng trên một ô, không thể tiếp nhiên liệu khi gặp nhau giữa đường. Hai xe không cản trở nhau.

Hãy tìm thời gian nhỏ nhất tính từ lúc bắt đầu để xe tuần tra đến quán. Nếu không thể đến quán, in -1.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên H, W — số hàng và số cột.
• H dòng tiếp theo, mỗi dòng gồm W số nguyên h[i][j] — độ cao của các ô.
• Dòng tiếp theo gồm sáu số nguyên x_1 y_1 x_2 y_2 x_3 y_3 — tọa độ xe tuần tra, xe tiếp nhiên liệu và quán Udon.
• Dòng cuối gồm hai số nguyên T, D — nhiên liệu ban đầu và lượng nhiên liệu được nạp thêm.

Các tọa độ được đánh số từ 1.

Dữ liệu ra

In thời gian nhỏ nhất để xe tuần tra đến quán; nếu không thể đến, in -1.

Ràng buộc

• 1 ≤ H, W ≤ 1000
• 0 ≤ h[i][j] ≤ 10^9
• 1 ≤ x_1, x_2, x_3 ≤ H
• 1 ≤ y_1, y_2, y_3 ≤ W
• 0 ≤ T, D ≤ 10^18

Phân nhóm điểm

1. (10 điểm) H, W ≤ 10.
2. (20 điểm) H, W ≤ 30.
3. (30 điểm) H, W ≤ 250.
4. (40 điểm) H, W ≤ 1000.

Ví dụ

Input

2 2
1 5
5 9
1 1 2 1 2 2
4 4

Output

8

Giải thích

Xe tuần tra đi từ (1, 1) đến (2, 1) mất 4 đơn vị thời gian. Xe tiếp nhiên liệu đã ở đó nên hai xe gặp nhau tại thời điểm 4; xe tuần tra được nạp thêm 4 đơn vị nhiên liệu. Sau đó, xe đi đến quán ở (2, 2), mất thêm 4 đơn vị. Tổng thời gian là 8.

Ví dụ 2

Input

8 8
0 1 2 3 4 5 6 7
10 11 12 13 14 15 16 17
20 21 22 23 24 25 26 27
30 31 32 33 34 35 36 37
40 41 42 43 44 45 46 47
50 51 52 53 54 55 56 57
60 61 62 63 64 65 66 67
70 71 72 73 74 75 76 77
1 1 8 1 8 8
43 34

Output

77

Một phương án tối ưu: xe tuần tra và xe tiếp nhiên liệu gặp nhau tại ô (5,4) vào thời điểm 43. Xe tiếp nhiên liệu đến đó sớm hơn và chờ. Sau khi nhận thêm 34 đơn vị nhiên liệu, xe tuần tra đi đến quán, đến nơi vào thời điểm 77.