시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB19612810774.825%

문제

갤러리의 지도는 M*N의 정사각형 격자로 표현될 수 있다. 어떤 정사각형들은 벽으로 구성되어 있고, 다른 정사각형들은 빈 공간으로 구성되어 있다. 벽을 회색, 빈 공간을 흰색으로 표현하면 다음 그림과 같다.

갤러리에 그림을 걸려고 한다. 그림의 길이는 정사각형의 변의 길이의 두 배이다. 반드시 빈 공간과 인접해 있는 벽에만 그림을 걸 수 있으며, 그림들은 서로 겹칠 수 없다. 갤러리의 맵이 주어졌을 때, 최대로 걸 수 있는 그림의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1 ≤ M, N ≤ 1,000) 다음 M개의 줄에는 각각 N개의 문자가 주어진다. 문자는 'X' 또는 '.'이며 'X'는 벽을, '.'는 빈 공간을 나타낸다.

입력되는 모든 데이터에서 적어도 첫 줄과 마지막 줄, 첫 열과 마지막 열은 모두 벽이다.

출력

최대 그림 개수를 출력한다.

예제 입력 1

3 3
XXX
X.X
XXX

예제 출력 1

0

예제 입력 2

5 5
XXXXX
X...X
X.XXX
X.X.X
XXXXX

예제 출력 2

4

예제 입력 3

7 10
XXXXXXXXXX
X.X.X....X
XXX.X.XX.X
XX....XX.X
X.XX..X..X
X..XX...XX
XXXXXXXXXX

예제 출력 3

14
W3sicHJvYmxlbV9pZCI6IjIxMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMjRcdWI3ZWNcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMyNFx1YjdlY1x1YjlhY1x1Yzc1OCBcdWM5YzBcdWIzYzRcdWIyOTQgTSpOXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NDAgXHViY2JkXHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NDAgXHViZTQ4IFx1YWNmNVx1YWMwNFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWJjYmRcdWM3NDQgXHVkNjhjXHVjMGM5LCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1ZDc3MFx1YzBjOVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWJhNzQgXHViMmU0XHVjNzRjIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNDY0MTliNTAtMjhjMy00ZDBkLTg5YjMtOWUyN2E0ZGMxM2IwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMDNweDsgaGVpZ2h0OiAxNDZweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzI0XHViN2VjXHViOWFjXHVjNWQwIFx1YWRmOFx1YjliY1x1Yzc0NCBcdWFjNzhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YmNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1YjQ1MCBcdWJjMzBcdWM3NzRcdWIyZTQuIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWJlNDggXHVhY2Y1XHVhYzA0XHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyOTQgXHViY2JkXHVjNWQwXHViOWNjIFx1YWRmOFx1YjliY1x1Yzc0NCBcdWFjNzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZGY4XHViOWJjXHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFjYjlcdWNlNjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhYzI0XHViN2VjXHViOWFjXHVjNzU4IFx1YjlmNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVhYzc4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZGY4XHViOWJjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzI0XHViN2VjXHViOWFjXHVjNzU4IFx1YzEzOFx1Yjg1YyBcdWFlMzhcdWM3NzQgTVx1YWNmYyBcdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE0sIE4gJmxlOyAxLDAwMCkgXHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBOXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YjI5NCAmIzM5O1gmIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTsuJiMzOTtcdWM3NzRcdWJhNzAgJiMzOTtYJiMzOTtcdWIyOTQgXHViY2JkXHVjNzQ0LCAmIzM5Oy4mIzM5O1x1YjI5NCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHViNDE4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM1ZDBcdWMxMWMgXHVjODAxXHVjNWI0XHViM2M0IFx1Y2NhYiBcdWM5MDRcdWFjZmMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNCwgXHVjY2FiIFx1YzVmNFx1YWNmYyBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNWY0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJjYmRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDVjXHViMzAwIFx1YWRmOFx1YjliYyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIxMTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHQUxFUklKQSIsImRlc2NyaXB0aW9uIjoiPHA+TWFwIG9mIGFuIGFydCBnYWxsZXJ5IGNhbiBiZSByZXByZXNlbnRlZCBieSBhIHNxdWFyZSBncmlkIG9mIE0gY29sdW1ucyBhbmQgTiByb3dzLiBTb21lIG9mIHRoZSBzcXVhcmVzIGFyZSB3YWxscyB3aGlsZSBvdGhlcnMgcmVwcmVzZW50cyBlbXB0eSBzcGFjZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Um9vbXMgY29uc2lzdCBvZiBhZGphY2VudCBmcmVlIHNxdWFyZXMgKHNxdWFyZXMgdGhhdCBzaGFyZSBlZGdlKS4gT24gdGhlIHdhbGxzIG9mIHRoZSByb29tcyB3ZSB3YW50IHRvIGhhbmcgYXMgbWFueSBwaWN0dXJlcyBhcyBwb3NzaWJsZS4gRXZlcnkgcGljdHVyZSBvY2N1cGllcyBleGFjdGx5IHR3byBsZW5ndGhzIG9mIGEgc3F1YXJlIGFuZCB0aGVpciBoZWlnaHQgZG9lc24mcnNxdW87dCBtYXR0ZXIuIEluIG90aGVyIHdvcmRzIHlvdSBjYW4gaGFuZyBhIHBpY3R1cmUgb24gdGhlIHdhbGwgaWYgdGhlcmUgYXJlIHR3byBjb25zZWN1dGl2ZSB3YWxscyBhbmQgdHdvIGZyZWUgc3F1YXJlcyBvcHBvc2l0ZSBvZiB0aGVtICh0aGF0IHR3byBmcmVlIHNxdWFyZXMgc2hvdWxkLCBvZiBjb3Vyc2UsIGJlIGF0IHRoZSBzYW1lIHNpZGUgb2Ygd2FsbHMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjb21wdXRlcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGljdHVyZXMgdGhhdCBjYW4gYmUgaGFuZ2VkIG9uIHRoZSB3YWxscy4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC80NjQxOWI1MC0yOGMzLTRkMGQtODliMy05ZTI3YTRkYzEzYjBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIwM3B4OyBoZWlnaHQ6IDE0NnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGlzIHBpY3R1cmUgc2hvd3Mgb25lIG9mIHRoZSBwb3NzaWJsZSBzb2x1dGlvbnMgZm9yIGEgZ2FsbGVyeSBtYXAuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSB0aGVyZSBhcmUgdHdvIGludGVnZXJzIE0gYW5kIE4sIDEgJmxlOyBNLE4gJmxlOyAxMDAwLCBudW1iZXIgb2YgdGhlIHJvd3MgYW5kIG51bWJlciBvZiB0aGUgY29sdW1ucyBvZiB0aGUgZ2FsbGVyeS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGhlIG5leHQgTSByb3dzIHRoZXJlIGFyZSBOIGNoYXJhY3RlcnMuIEV2ZXJ5IGNoYXJhY3RlciByZXByZXNlbnRzIGVpdGhlciBhIGZyZWUgc3F1YXJlIG9yIHdhbGwuICZsc3F1bztYJnJzcXVvOyByZXByZXNlbnRzIHdhbGwgYW5kICZsc3F1bzsuJnJzcXVvOyByZXByZXNlbnRzIGZyZWUgc3BhY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpcnN0IGFuZCBsYXN0IHJvdywgYXMgd2VsbCBhcyBmaXJzdCBhbmQgbGFzdCBjb2x1bW4gYXJlIHdhbGxzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIGZpbGUgeW91IHNob3VsZCB3cml0ZSBtYXhpbXVtIG51bWJlciBvZiBwaWN0dXJlcyB0aGF0IGNhbiBiZSBoYW5nZWQgb24gd2FsbHMgb2YgZ2FsbGVyeTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=