JOI IOI-дың бейресми кездесуіне қатысып жатыр. Кездесуде сэндвичтер $R$ жол мен $C$ бағаннан тұратын тордың бойымен орналастырылған. Әрбір сэндвич екі қабырғасы тор ұяшығының қабырғасының ұзындығына тең болатын теңбүйірлі тікбұрышты үшбұрыш пішіндес, және әр ұяшықта гипотенузалары бір-біріне тиіп тұратындай етіп қойылған екі сэндвич бар. Төмендегі суретте сэндвичтердің орналасу мысалы көрсетілген.

1-сурет. Сэндвичтердің орналасу мысалы

Егер сэндвич келесі екі шартты да қанағаттандырса, оны алуға болмайды: Оның гипотенузасы әлі алынбаған басқа бір сэндвичке тиіп тұр. Оның гипотенузадан басқа екі қабырғасының кемінде біреуі әлі алынбаған басқа бір сэндвичке тиіп тұр.

Бұлардан басқа сэндвичтерді алуға болады.

Ешбір сэндвич алынбаған күй бастапқы күй болып табылады. Бастапқы күйден белгілі бір сэндвичті алу үшін алдымен басқа сэндвичтерді алу қажет болуы мүмкін. Сэндвичтердің орналасуына байланысты кейбір сэндвичтерді мүлдем алу мүмкін болмауы да ықтимал.

JOI бір ұяшықта орналасқан екі сэндвичті де жегісі келеді. Ол әлі қай ұяшықтың сэндвичтерін жейтінін шешкен жоқ.

Оны бастапқы күйден белгілі бір ұяшықтағы екі сэндвичті де алу үшін кем дегенде қанша сэндвич алу керек екені қызықтырады.

Тапсырма

Сэндвичтердің орналасуы берілген. Әрбір ұяшық үшін бастапқы күйден бірнеше сэндвичті алу арқылы сол ұяшықтағы екі сэндвичті де алуға болатынын не болмайтынын анықтаңыз. Егер бұл мүмкін болса, алу қажет болатын сэндвичтердің ең аз санын табыңыз. Сэндвичтердің санына мақсатты екі сэндвичтің өздері де кіруі тиіс екенін ескеріңіз.

Кіріс деректер

Стандартты енгізуден келесі деректерді оқыңыз: Бірінші жолда бос орын арқылы бөлінген екі бүтін сан $R$ және $C$ берілген. Олар сэндвичтердің $R$ жол мен $C$ бағаннан тұратын тор бойымен орналасқанын білдіреді. Келесі $R$ жолдың $i$-ші жолында ($1 \le i \le R$) ұзындығы $C$ болатын жол берілген. Әрбір таңба 'N' немесе 'Z' болып табылады. Бұл жолдың $j$-ші таңбасы ($1 \le j \le C$) жоғарыдан санағанда $i$-ші жолда және сол жақтан санағанда $j$-ші бағанда орналасқан ұяшықтағы сэндвичтердің орналасуын білдіреді. 'N' және 'Z' сәйкесінше келесі орналасуларды білдіреді.

2-сурет. Әр ұяшықтағы сэндвичтердің орналасуы

Шығыс деректер

Стандартты шығаруға $R$ жол шығарыңыз. $i$-ші жолда ($1 \le i \le R$) бос орын арқылы бөлінген $C$ бүтін сан болуы тиіс. $j$-ші бүтін сан ($1 \le j \le C$) жоғарыдан санағанда $i$-ші жолда және сол жақтан санағанда $j$-ші бағанда орналасқан ұяшықтағы екі сэндвичті де алу үшін қажет сэндвичтердің ең аз саны болуы тиіс. Егер оларды алу мүмкін болмаса, -1 шығарыңыз.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады: $1 \le R \le 400$ $1 \le C \le 400$

Ішкі тапсырмалар

1-ішкі тапсырма [35 ұпай]

• $R \le 50$
• $C \le 50$

2-ішкі тапсырма [65 ұпай]

• Қосымша шектеулер жоқ.

Мысалдар

Кіріс 1

2 3
NZN
ZZN

Шығыс 1

10 8 2
8 6 4

Ескертпе 1

1-мысалдағы сэндвичтердің орналасуы есеп шартындағы 1-суретке сәйкес келеді. Мысалы, жоғарыдан 2-ші жолда және сол жақтан 2-ші бағанда орналасқан ұяшықтағы екі сэндвичті алу үшін сэндвичтерді келесі ретпен алуға болады: 1-ші жол, 3-ші бағандағы ұяшықтың оң жақ жоғарғы сэндвичін алу. 1-ші жол, 3-ші бағандағы ұяшықтың сол жақ төменгі сэндвичін алу. 2-ші жол, 3-ші бағандағы ұяшықтың оң жақ жоғарғы сэндвичін алу. 2-ші жол, 3-ші бағандағы ұяшықтың сол жақ төменгі сэндвичін алу. 2-ші жол, 2-ші бағандағы ұяшықтың оң жақ төменгі сэндвичін алу. 2-ші жол, 2-ші бағандағы ұяшықтың сол жақ жоғарғы сэндвичін алу.

Барлығы 6 сэндвич алынады, және бұл ең аз сан болғандықтан, 6 шығарылады.

Кіріс 2

2 2
NZ
ZN

Шығыс 2

-1 -1
-1 -1

Ескертпе 2

Бұл жағдайда сэндвичтердің ешқайсысын алу мүмкін емес.

Кіріс 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Шығыс 3

10 12 14 16 2
8 -1 -1 -1 4
6 -1 -1 -1 6
4 -1 -1 -1 8
2 16 14 12 10