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

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

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

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

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

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