Trên một bàn cờ kích thước ~8 \times 8~ có ~k~ quân hậu đen và một quân mã trắng. Các hàng và cột của bàn cờ đều được đánh số từ ~1~ đến ~8~.

Mỗi ô trên bàn cờ có một giá trị phần thưởng. Quân mã bắt đầu từ một ô cho trước. Khi quân mã đi vào một ô, nó nhận được phần thưởng của ô đó nếu trước đó chưa từng nhận phần thưởng ở ô này. Quân mã được phép đi lại vào ô cũ, nhưng phần thưởng của mỗi ô chỉ được nhận nhiều nhất một lần.

Quân hậu không di chuyển, trừ khi bị quân mã ăn. Một quân hậu khống chế tất cả các ô cùng hàng, cùng cột và cùng đường chéo với nó.

Quân mã di chuyển theo hình chữ L. Từ ô ~(x, y)~, quân mã có thể đi đến một trong các ô:

• ~(x - 2, y - 1)~
• ~(x - 2, y + 1)~
• ~(x - 1, y - 2)~
• ~(x - 1, y + 2)~
• ~(x + 1, y - 2)~
• ~(x + 1, y + 2)~
• ~(x + 2, y - 1)~
• ~(x + 2, y + 1)~

ảnh minh họa

Quân mã được đi tối đa ~n~ bước. Mỗi bước phải đi đến một ô nằm trong bàn cờ.

Quân mã không được đi vào một ô trống đang bị quân hậu khống chế. Nếu ô đích đang có một quân hậu, quân mã được phép ăn quân hậu đó khi quân hậu này không được bất kỳ quân hậu nào khác bảo vệ. Sau khi bị ăn, quân hậu bị loại khỏi bàn cờ và không còn khống chế ô nào nữa. Dữ liệu đảm bảo ban đầu quân mã không nằm ở ô đang bị quân hậu khống chế. Không có ô nào có nhiều hơn một quân cờ.

Hãy tính tổng phần thưởng lớn nhất mà quân mã có thể nhận được sau không quá ~n~ bước đi.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~, lần lượt là số bước đi tối đa của quân mã và số quân hậu trên bàn cờ.
• ~8~ dòng tiếp theo, mỗi dòng chứa ~8~ số nguyên. Số thứ ~j~ trên dòng thứ ~i~ là phần thưởng của ô ~(i, j)~.
• ~k~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ là vị trí của một quân hậu.
• Dòng cuối cùng chứa hai số nguyên ~s_x, s_y~ là vị trí ban đầu của quân mã.

Output

In ra một số nguyên duy nhất là tổng phần thưởng lớn nhất mà quân mã có thể nhận được.

Sample

Sample Input 1

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
2 4
2 6
4 5
1 1

Sample Output 1

8

Constraints

• ~0 < n \le 10~
• ~0 < k \le 4~
• Các quân hậu và quân mã ban đầu nằm trong bàn cờ.
• Không có hai quân hậu nào đứng trên cùng một ô.
• ~0 \le~ phần thưởng của mỗi ô ~\le 100~