치즈학

당신은 개미입니다. 그냥 개미가 아니라 치즈에 푹 빠진 개미입니다.

주방에서 새로운 치즈 조각을 발견했고, 가능한 한 많은 부하를 보내 이 치즈를 조사하려고 합니다. 치즈는 $N$개의 행과 $M$개의 열로 이루어진 표로 생각할 수 있습니다. 행은 위에서 아래로 1부터 $N$까지, 열은 왼쪽에서 오른쪽으로 1부터 $M$까지 번호가 매겨져 있습니다. $r$행 $s$열의 칸은 $(r, s)$로 씁니다. 일부 칸에는 구멍이 있고 나머지는 치즈입니다. 왼쪽 위 칸과 오른쪽 아래 칸은 반드시 치즈입니다.

부하의 수를 $K$라고 합시다. 부하들은 왼쪽 위 칸에서 출발해 오른쪽 아래 칸에서 끝냅니다. 부하는 아래 방향과 오른쪽 방향으로만 이동할 수 있습니다. 경로는 서로 교차하면 안 됩니다. 부하에게 1부터 $K$까지 번호를 붙였을 때, 어떤 칸에서도 번호가 작은 부하는 오른쪽으로 나가고 번호가 큰 부하는 같은 칸에서 아래로 나가는 일이 없어야 합니다.

또한 경로들이 서로 다른 쪽으로 갈라져야 합니다. 임의의 두 부하에 대해, 구멍이 있는 칸 $(r, s)$가 존재해서, 한 부하는 어느 시점에 열 $s$에서 행 번호가 $r$보다 작은 곳에 있었고, 다른 부하는 (같은 시점일 필요는 없이) 열 $s$에서 행 번호가 $r$보다 큰 곳에 있었어야 합니다. 쉽게 말해, 두 부하는 어떤 구멍을 서로 반대편에서 돌아간 것입니다.

위 조건을 만족하는 경로를 고를 수 있는 가장 큰 $K$를 출력하세요.

조건을 만족하지 않는 경로의 예는 아래와 같습니다.

(a) 잘못된 경로 선택: 경로가 서로 교차함	(b) 잘못된 경로 선택: 두 경로가 구멍을 같은 쪽으로 돌아감

첫 줄에 자연수 $N$과 $M$이 주어집니다.

이어지는 $N$개의 줄에는 표의 각 행이 주어집니다. 각 줄은 $M$개의 문자로 이루어져 있으며, .는 치즈, #는 구멍이 있는 칸을 나타냅니다.

조건을 만족하도록 경로를 고를 때 가능한 $K$의 최댓값을 한 줄에 출력합니다.

모든 서브태스크에서 $2 \le N, M \le 2000$입니다.

샘플 테스트 설명:

(a) 첫 번째 샘플의 경로 선택 예	(b) 두 번째 샘플의 경로 선택 예