Cho một bàn cờ vua kích thước N x N. Chi phí khi đi qua ô (i,j) bằng A[i][j].

Nhiệm vụ của bạn là hãy tìm một đường đi cho quân Mã từ ô (s, t) tới ô (u, v) sao cho chi phí là nhỏ nhất. Nếu quân Mã không thể đi tới ô đích thì hãy in ra -1.

Đầu vào

• Dòng 1 bắt đầu bởi hai số nguyên N và s, t, u, v.

• N dòng tiếp theo, mỗi dòng gồm N số nguyên A[i][j]

Giới hạn

• 1 ≤ N, M ≤ 15

• 0 ≤ A[i][j] ≤ 100

Đầu ra

• In ra một số nguyên là chi phí nhỏ nhất cho đường đi tìm được.

Ví dụ :

Input 01

13
3 2 3 11
52 6 72 11 51 33 1 14 69 60 41 80 61 
66 38 51 29 63 54 19 86 53 67 91 94 34 
41 73 70 10 37 44 12 30 67 59 46 53 33 
4 40 78 23 66 90 26 7 31 25 59 30 96 
7 70 6 30 57 93 25 57 97 31 94 15 41 
16 87 67 82 96 3 55 4 23 20 35 89 59 
51 90 64 5 62 85 4 40 87 2 93 51 100 
39 43 89 63 65 76 71 66 95 35 20 97 62 
2 96 15 97 51 43 18 100 47 55 11 74 10 
61 45 87 87 40 57 7 39 19 58 33 80 99 
86 23 24 59 4 91 29 28 72 49 8 40 56 
41 29 95 12 35 33 40 84 69 82 56 36 1 
86 1 28 68 39 65 77 51 10 61 77 40 79

Output 01

194