Problem description

Na planszy o wymiarach n × n znajdują się:

• . - wolne pole, na którym można postawić Pac‑Mana,
• # - pole zablokowane,
• cyfra c (od 1 do k) - oznaczenie początkowej pozycji duszka nr c.

Każdy z k duszków porusza się ruchem czterokierunkowym (góra, dół, lewo, prawo), nie może wchodzić na pola zablokowane i ma przypisaną prędkość s_i, czyli pokonuje s_i pól w ciągu jednej sekundy.

Chcemy wybrać wolne pole (.) na planszy tak, aby maksymalnie opóźnić moment, w którym któryś z duszków dosięgnie Pac‑Mana. Duszki wyruszają natychmiast ze swoich początkowych pozycji i poruszają się w kierunku Pac‑Mana najkrótszą dostępną ścieżką. Pac-man postawiony na pewnej pozycji będzie na niej czekał, aż do momentu jak złapie go jakiś duszek.

Dla dowolnego pola p i duszka i czas dojścia obliczamy jako: $$ \left\lceil \frac{d(z_i, p)}{s_i} \right\rceil $$ gdzie d(z_i,p) to długość najkrótszej ścieżki od startowego pola duszka i do pola p, a s_i to prędkość duszka.

Chcemy udzielić odpowiedzi na t przypadków testowych.

Wejście

Pierwsza linia wejścia: t — liczba przypadków testowych.

Dla każdego z t przypadków:

• n, k — liczby całkowite opisujące wymiar planszy i liczbę duszków.
• Następnie n wierszy: każdy zawiera n znaków: . # lub cyfrę od 1 do k.
• Ostatnia linia: k liczb całkowitych s₁, s₂, …, s_k — prędkości kolejnych duszków.

Gwarantowane:

• Na planszy jest co najmniej jedno wolne pole (.).
• Każda cyfra od 1 do k występuje dokładnie raz.

Wyjście

• Jeśli istnieje wolne pole nieosiągalne dla żadnego duszka, wypisz: NIE

• W przeciwnym razie wypisz pojedynczą liczbę całkowitą — maksymalny czas w sekundach, po którym Pac‑Man zostanie złapany.

Ograniczenia

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 9
• 1 ≤ s_i ≤ 100
• Suma wartości n we wszystkich przypadkach testowych nie przekroczy 5 000

Przykład

2
3 1
1..
..#
.#.
1
3 2
1#2
.#.
...
1 3

NIE
2