Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

E. Эвакуация
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Опять они там что-то напортачили... В одном из ядерных реакторов исследовательской станции идет неуправляемая реакция и скоро произойдет взрыв, который уничтожит всю станцию.

Станция представляет собой квадрат n × n разбитый на блоки 1 × 1. Каждый блок является или реактором или лабораторией. Реакторов может быть несколько и ровно один из них собирается взорваться. Реакторы можно считать непроходимыми блоками, по лабораториям же можно перемещаться. Между любыми двумя лабораториями, которые находятся в соседних блоках, имеется коридор. Блоки считаются соседними, если имеют общее ребро.

В каждой из лабораторий имеется некоторое количество ученых и некоторое количество спасательных капсул. Как только ученый залезает в капсулу, он считается спасенным. В каждую капсулу помещается не более одного ученого.

Реактор, который скоро взорвется, поврежден и из него вытекает токсичная охлаждающая жидкость в соседние блоки. Блок, в котором расположен этот реактор, считается зараженным. Каждую минуту охлаждающая жидкость растекается по лабораториям через коридоры. Если в какую-то минуту один из блоков заражен, то на следующую минуту все соседние лаборатории также оказываются заражены. Как только лаборатория оказывается заражена, все ученые в ней, которые находятся не в спасательных капсулах, погибают. Через блоки с реакторами охлаждающая жидкость не распространяется.

До взрыва осталось ровно t минут. Любой ученый за одну минуту может переместиться по коридору в соседнюю лабораторию, если она не заражена. По любому коридору одновременно могут перемещаться неограниченное количество ученых в обоих направлениях. Считается, что ученые внутри лаборатории перемещается без затрат времени. Кроме того, любой ученый может залезть в спасательную капсулу мгновенно. Также считается, что любой ученый в данную минуту всегда успевает сделать свои действия (переместиться из данной лаборатории в соседнюю или залезть в спасательную капсулу) до того, как лаборатория окажется заражена.

Определите максимальное количество ученых, которым удастся спастись.

Входные данные

В первой строке находятся два целых числа n и t (2 ≤ n ≤ 10, 1 ≤ t ≤ 60). В каждой из последующих n строк находится по n символов — описание расположения ученых. Затем идет ровно одна пустая строка. После этого идет еще n строк по n символов в каждой — описание расположения спасательных капсул.

В описаниях расположения ученых и спасательных капсул символ «Y» означает исправно работающий реактор, «Z» — поврежденный реактор. Расположения реакторов в обоих описаниях совпадают. На станции имеется ровно один поврежденный реактор. Символами «0» - «9» обозначаются лаборатории. В описании расположения ученых эти символы обозначают количество ученых в соответствующих лабораториях. В описании спасательных капсул — количество этих капсул в каждой из лабораторий.

Выходные данные

Выведите одно целое число — максимальное количество ученых, которым удастся спастись.

Примеры
Входные данные
3 3
1YZ
1YY
100

0YZ
0YY
003
Выходные данные
2
Входные данные
4 4
Y110
1Y1Z
1Y0Y
0100

Y001
0Y0Z
0Y0Y
0005
Выходные данные
3
Примечание

Во втором примере события могли происходить следующим образом: