주차 파티

페이먼은 자볼에 있는 자기 집에서 저녁 파티를 열기로 했다. 그의 집에는 직사각형 주차장이 있으며, 이는 $n$행 $m$열의 격자로 나타낼 수 있다. 자동차는 $n \times m$개의 칸 중 하나에 주차할 수 있다. 일부 칸에는 움직일 수 없는 기둥이 있어서, 자동차는 그 칸에 주차하거나 그 칸을 지나갈 수 없다. 각 행과 각 열의 양 끝에는 입구가 하나씩 있다. 자동차가 입구로 들어오면 그 행이나 열을 따라 곧장 앞으로 움직인다. 반대편 입구에 도달하거나, 다음 칸이 기둥이나 이미 주차된 다른 차로 막혀 있으면 멈추고 주차한다. 첫 번째 칸이 이미 차 있는 행이나 열에는 들어갈 수 없다.

페이먼은 주차장에 가능한 한 많은 차를 세우고 싶어 한다. 그는 도착하는 손님에게 어느 입구로 들어갈지 지시할 수 있다. 페이먼이 이 목표를 이루도록 도와라.

첫 줄에 행의 수 $n$과 열의 수 $m$이 공백으로 구분된 정수로 주어진다 ($1 \leq n, m \leq 1000$). 다음 $n$줄에는 각각 "."과 "o"로만 이루어진 길이 $m$의 문자열이 주어진다. $(i+1)$번째 줄의 $j$번째 문자가 "o"이면 $i$행 $j$열 칸에 기둥이 있고, "."이면 그 칸은 비어 있다.

페이먼이 주차장에 세울 수 있는 자동차의 최대 대수 $k$를 한 줄에 출력하라.