대피

또 무언가를 망쳐 놓았다... 연구 기지의 한 원자로에서 통제되지 않는 반응이 진행 중이며, 곧 기지 전체를 파괴할 폭발이 일어난다.

기지는 1 × 1 블록으로 나뉜 n × n 크기의 정사각형으로 나타낸다. 각 블록은 원자로이거나 실험실이다. 원자로는 여러 개일 수 있으며, 그중 정확히 하나가 곧 폭발한다. 원자로는 통과할 수 없는 블록으로 간주하지만, 실험실은 통과해 이동할 수 있다. 인접한 블록에 있는 임의의 두 실험실 사이에는 복도가 있다. 공통 변을 가지는 블록은 인접한 것으로 간주한다.

각 실험실에는 일정한 수의 과학자와 일정한 수의 구조 캡슐이 있다. 과학자가 캡슐에 들어가면 구조된 것으로 간주한다. 각 캡슐에는 최대 한 명의 과학자만 들어갈 수 있다.

곧 폭발할 원자로는 손상되어 있으며, 그곳에서 유독성 냉각수가 이웃 블록으로 흘러든다. 원자로가 있는 블록은 오염된 것으로 간주한다. 냉각수는 매분 복도를 통해 실험실로 퍼진다. 어떤 순간에 한 블록이 오염되어 있다면, 다음 분에 그 블록과 인접한 모든 실험실도 오염된다. 실험실이 오염되면 그곳에서 구조 캡슐에 들어가 있지 않은 모든 과학자가 죽는다. 냉각수는 원자로 블록을 통과해 퍼지지 않는다.

폭발까지 정확히 t분이 남아 있다. 각 과학자는 일 분 동안 복도를 따라 감염되지 않은 다음 실험실로 이동할 수 있다. 모든 복도에서는 제한 없이 많은 과학자가 양방향으로 동시에 이동할 수 있다. 과학자가 실험실 내부에서 이동하는 데에는 시간이 들지 않는다고 간주한다. 또한 모든 과학자는 구조 캡슐에 즉시 들어갈 수 있다. 그리고 임의의 순간에 모든 과학자는 실험실이 오염되기 전에 자신의 행동, 즉 현재 실험실에서 다음 실험실로 이동하거나 구조 캡슐에 들어가는 행동을 수행할 시간이 항상 있다고 간주한다.

탈출할 수 있는 과학자 수의 최댓값을 구한다.

첫 번째 줄에 두 정수 n와 t가 주어진다 (2 ≤ n ≤ 10, 1 ≤ t ≤ 60). 다음 n개의 각 줄에는 n개의 문자가 주어진다. 이 줄들은 과학자들의 위치를 나타낸다. 그다음 정확히 하나의 빈 줄이 주어진다. 이어지는 n개의 각 줄에는 n개의 문자가 주어진다. 이 줄들은 구조 캡슐의 위치를 나타낸다.

과학자와 구조 캡슐의 위치를 나타내는 설명에서 문자 "Y"는 정상적으로 작동하는 원자로를, "Z"는 고장 난 원자로를 나타낸다. 두 설명에서 원자로의 위치는 일치한다. 기지에는 고장 난 원자로가 정확히 하나 있다. 숫자 "0" - "9"는 실험실을 나타낸다. 과학자 위치에 대한 설명에서 이 숫자는 해당 실험실에 있는 과학자의 수를 나타낸다. 구조 캡슐에 대한 설명에서는 각 실험실에 있는 구조 캡슐의 수를 나타낸다.

자신을 구하는 데 성공할 과학자 수의 최댓값을 하나의 수로 출력한다.

두 번째 예제에서는 사건이 다음과 같이 진행될 수 있다: