Amous là một cao thủ CP và là đệ tử ruột của admin CaiWinDao. Để nâng cao IQ cho đệ tử mình, CaiWinDao luôn đưa ra những câu đố "hóc búa" để thử tài Amous. Với tài trí của mình, trừ những lần ngây ngô bị lừa ra thì còn lại anh ấy đều có thể dễ dàng vượt qua. Sáng nay trong lúc giao lưu Cờ Vua với đệ tử, CaiWinDao lại nảy ra một câu đố như sau:

Trên bàn Cờ Vua tiêu chuẩn (\(8\times8\)) đặt \(k\) quân Hậu đen (không nằm đè lên nhau) và \(1\) quân Mã trắng. Những ô trên bàn cờ không được đặt các quân cờ thì sẽ được đặt những giá trị phần thưởng khác nhau. Các quân Hậu đen không được di chuyển. Quân Mã được phép di chuyển \(n\) bước theo luật Cờ Vua, nhưng không được đi vào những ô đang bị sự kiểm soát của các Quân Hậu (mỗi quân Hậu sẽ kiểm soát hàng, cột và hai đường chéo nó đang đứng). Khi Mã đi vào ô nào thì sẽ thu được giá trị phần thưởng trong ô đó, phần thưởng của mỗi ô chỉ được lấy một lần. Quân Mã có quyền ăn những quân Hậu không được bảo vệ bởi quân Hậu khác, và sau khi quân Hậu được ăn những ô mà nó kiểm soát sẽ được giải phóng (nếu không bị kiểm soát bởi những quân Hậu khác). Dữ liệu luôn đảm bảo ô quân Mã đứng không bị kiểm soát và nó có thể di chuyển. Hãy tính tổng giá trị phần thưởng lớn nhất mà quân Mã có thể thu được sau khi di chuyển \(n\) bước.

Phần thưởng được đưa ra khi giải được bài toán này chính là quyển bí kíp tuyệt học "Tán gái thần công" của CaiWinDao. Bài toán này có vẻ quá đơn giản với một cao thủ CP như Amous, nhưng sau "cuộc đại chiến" VOI vừa qua anh ấy đã quyết định "rửa tay gác kiếm" một thời gian để hồi sức. Chính vì vậy anh muốn nhờ đến sự giúp đỡ của bạn để giành được cuốn bí kíp.

Lưu ý: Tọa độ của các quân cờ sẽ được biểu diễn theo quy ước tiêu chuẩn của Cờ Vua, ví dụ ô "\(E5\)" sẽ là ô ở cột \(E\) hàng \(5\). Hàng sẽ được đánh số từ \(1\) đến \(8\) từ trên xuống dưới và cột từ \(A\) đến \(H\) từ trái qua phải.

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(k\) lần lượt là số bước di chuyển của quân Mã và số quân Hậu trên bàn cờ.
• Tiếp theo là \(8\) dòng, mỗi dòng gồm \(8\) giá trị mô tả phần thưởng của ô tương ứng (các ô chứa quân cờ sẽ có giá trị bằng \(0\)).
• Sau đó là \(k\) dòng biểu diễn tọa độ của \(k\) quân Hậu đen.
• Cuối cùng là một dòng biểu diễn tọa độ của quân Mã trắng.

Output

• In ra một số duy nhất là tổng giá trị phần thưởng lớn nhất mà quân Mã có thể thu được.

Ví dụ

Sample input

10 3
0 7 23 14 10 9 12 3
7 9 13 0 4 0 8 1
3 8 1 17 9 20 5 4
0 11 6 6 0 32 4 5
11 18 5 19 21 27 33 12
3 7 19 22 31 20 10 3
1 15 25 17 21 10 20 7
8 14 23 12 0 1 10 11
D2
F2
E4
A1

Sample output

8

Giải thích ví dụ

Những ô được tô màu đỏ là ô đã bị kiểm soát bởi Hậu. Quân Mã chỉ có thể di chuyển qua lại giữa hai ô \(A1\) và \(B3\), các quân Hậu đều bảo vệ nhau nên quân Mã không thể tấn công bất cứ quân nào để thoát ra. Phần thưởng trên ô \(B3\) chỉ được thu một lần nên tổng giá trị lớn nhất có thể thu được là \(8\).

Ràng buộc

• \(0<n\leq10\).
• \(0<k\leq4\)
• Giá trị trong mỗi ô là số nguyên không âm và \(\leq100\).